Pages

Wednesday, November 9, 2011

How to install the SSL module for the AppEngine SDK on OS X

AppEngine SDKs for Python and Go both depend on the Python 2.5 runtime, which does not include the ssl module out of the box. Without the ssl module, you'll see the following warnings when you run dev_appserver.py or appcfg.py:

WARNING urlfetch_stub.py:111 No ssl package found. urlfetch will not be able to validate SSL certificates.

WARNING appengine_rpc.py:435 ssl module not found.
Without the ssl module, the identity of the remote host cannot be verified, and
connections may NOT be secure. To fix this, please install the ssl module from
http://pypi.python.org/pypi/ssl .


Here's how to fix it.
  1. Download the ssl source for Python 2.5 from http://pypi.python.org/pypi/ssl#downloads and uncompress the package.
  2. From that directory, run:
    CC='/usr/bin/gcc-4.0' python2.5 setup.py build

    sudo python2.5 setup.py install
  3. Done. No more pesky security warnings.

Sunday, September 18, 2011

Go Template Examples

The Go language's template package has introduced a set of new APIs in r60. (To keep using the old template package, you'll need to change import "template" to import "old/template".) This post includes a collection of code snippets to illustrate how to use the new template package.

Parse a template string

t, _ := template.New("template_name").Parse("Go")
t.Execute(os.Stdout, nil)

// output: Go

Parse a template file

t, _ := template.New("template_name").ParseFile("external.file")
t.Execute(os.Stdout, nil)

// output: content of external.file

Print to a string buffer

t, _ := template.New("template_name").Parse("Go")
buf := new(bytes.Buffer)
t.Execute(buf, nil)

// buf.String() == "Go"

Substitute a single parameter

t, _ := template.New("template_name").Parse("<h1>{{.}}</h1>")
t.Execute(os.Stdout, "Joseki")

// output: <h1>Joseki</h1>

Substitute multiple parameters in a struct

type dict struct {
  // struct fields must be public
  Title string
  Release int
}
params := &dict{Title: "Go", Release: 60}
t, _ := template.New("template_name").Parse(
    "<h1>{{.Title}}</h1>r{{.Release}}")
t.Execute(os.Stdout, params)

// output: <h1>Go</h1>r60

Substitute multiple parameters in a map

t, _ := template.New("template_name").Parse(
    "<h1>{{.title}}</h1>r{{.release}}")
// field names don't have to be capitalized
params := map[string]interface{}{"title": "Go", "release": 60}
t.Execute(os.Stdout, params)

// output: <h1>Go</h1>r60

Conditionally fill in parameters

t, _ := template.New("template_name").Parse(
    "{{if .white}}Gote{{else}}Sente{{end}}{{if .excl}}!{{end}}")
t.Execute(os.Stdout, map[string]bool{"excl": true})

// output: Sente!

Iteratively fill in parameters

t, _ := template.New("template_name").Parse(
    "{{range .}}{{.}}!{{else}}Tengen{{end}}")
t.Execute(os.Stdout, [...]string{"Hoshi", "Komoku", "Sansan"})

// output: Hoshi!Komoku!Sansan!

Escape parameters

t, _ := template.New("html").Parse(
    "<a href='/?q={{.query | urlquery}}'>q={{.text | html}}</a>")
t.Execute(os.Stdout, map[string]string{"text": "&", "query": "&"})

// output: <a href='/?q=%26'>q=&amp;</a>

Nest templates (deprecated API)

ts := new(template.Set)
tparent, _ := template.New("parent").Parse(
    "<i>{{template \"child\" .}}</i>")
tchild, _ := template.New("child").Parse(
    "<b>{{.lang}}</b>")
ts.Add(tparent, tchild)
ts.Execute(os.Stdout, "parent", map[string]string{"lang": "Go"})

// output: <i><b>Go</b></i>

Parse a template set (deprecated API)

ts := new(template.Set)
ts.Parse(`{{define "parent"}}<i>{{template "child" .}}</i>{{end}}
    {{define "child"}}<b>{{.lang}}</b>{{end}}`)
ts.Execute(os.Stdout, "parent", map[string]string{"lang": "Go"})

// output: <i><b>Go</b></i>

Nested templates

t, _ := template.New("parent").Parse(`<i>{{template "child" .}}</i>`)
t.New("child").Parse(`<b>{{.lang}}</b>`)
t.ExecuteTemplate(os.Stdout, "parent", map[string]string{"lang": "Go"})
// output: <i><b>Go</b></i>

Defined templates

t, _ := template.New("").Parse(
    `{{define "golang"}}golang{{end}} {{define "go"}}Go{{end}}`)
t.ExecuteTemplate(os.Stdout, "go", nil)
// output: Go
The template package also offers a few more APIs not covered by the examples. Please refer to the documentation for more information.

Tuesday, June 21, 2011

Saaguan Paradox

A new entry for Daniel Solis' thousand year game design challenge caught my attention today. It's an interesting abstract board game called Saaguan, designed by Andrew Cooke.

Full rules can be found here. In a nutshell, players maneuver their robots on an oct-board or hex-board to kill other robots. Each robot emits a beam toward where it's heading for, threatening enemy bots along the line. If a bot is threatened by two enemy bots, it gets "locked down", and its beam is immediately disabled; if a bot is threatened by three enemies, it gets killed and immediately removed from the board. On each turn, a player can either add a new bot to the board or make three movements of existing bots of their own by rotation or advancement.

I was quickly intrigued by Saaguan's simple rules and the difficulty to write a decent A.I. player due to its huge branching factor even on very small boards. When I started to mull over an algorithm to detect locked down and dead bots, it then occurred to me that certain contrived bot move sequences would expose an ambiguity in Saaguan's rules.

Let's consider an example on an oct-board.


In the previous diagram, blue bot #2 and #4 both threaten red bot #3, therefore locking it down (marked by a black border).


When bot #5 and #6 join the battlefield as shown above, blue bot #2 gets locked down, freeing red bot #3.


Blue turns the table again with the reinforcement of bot #7.


The addition of red bot #8 rescues neither #3 nor #6 as red is short of one more beam to lock down blue bot #7.


Here comes an interesting turning point: What happens if blue bot #2 now rotates by 90 degrees?

One might examine bot #3 first and conclude that since #2 is no longer threatening it, #3 becomes active and locks down #7 with the help of #8. One might even argue that before #2 reorients its beam downward, #6 has a chance to lock down #2 together with #1 since #7's threat is dissolved.

On the other hand, one might also check the state of bot #6 first and claim that it's under a three-way attack from #2, #5, #7 and should be immediately killed.

As this example has shown, the order of state changes is critical in evaluating delicate Saaguan situations, which hopefully will be addressed by an updated rule set.

Update

Andrew has already disambiguated the rules on his site. That was fast!

Also, I made a mistake in the original example — robots on octboards rotate by 45° on each turn, not 90°. An updated example follows:


Red-a is locked down by Blue-b and Blue-c; Red-d by Blue-e and Blue-g. Now Blue-c rotates clockwise by 45°. Depending on the order of state evaluation, either Red-d or Blue-e could be said to be shut down. According to the new rules — if I'm interpreting them correctly — once Blue-c starts to rotate, Red-a gets activated, thus locking down Blue-e, which in turn activates Red-d. Blue-e then gets shut down before Blue-c points to the right and locks down Red-d.

Wednesday, March 30, 2011

Creating large in-memory database on AppEngine

For high performance AppEngine app development, it often comes in handy to store read-only database in memory. Accessing in-memory data is not only orders of magnitude faster than making DataStore or memcached calls but also a lot cheaper as it does not incur any API cost.

However, if you encode data as a Python dictionary or list with a million entries, your app will most likely crash on AppEngine, throwing a distasteful exceptions.MemoryError: Exceeded soft process size limit with 299.98 MB. "But I'm only loading 10MB of data!", you proclaim. Unfortunately, Python may temporarily consume over a gigabyte of memory while parsing and constructing a multi-megabyte dictionary or list.

The first thing you should consider is to simplify the data structure. If possible, flatten your database into one-dimensional lists, which enjoy a smaller memory footprint than dictionaries and multi-level nested lists.

Next, try data serialization using the pickle library. Be sure to use protocol version 2 for maximum efficiency and compactness. For example:
# To serialize data
pickle.dump(data, open('data.bin', 'w'), pickle.HIGHEST_PROTOCOL)
# To deserialize data
data = pickle.load(open(os.path.join(os.path.dirname(__file__), 'data.bin'), 'r'))


As AppEngine does not support the much faster cPickle module ("cPickle" is aliased to "pickle" on AppEngine), your app may time out if you try to unpickle millions of records. One effective solution is to store your data in homogeneous arrays to take advantage of array's highly efficient serialization implementation. Suppose you have a list of a million signed integers, you may first convert the list into a typed array and save it in a binary file:
array.array('i', data).tofile(open('data.bin', 'w'))
Deserializing the array literally takes just a few milliseconds on AppEngine:
data = array.array('i')
data.fromfile(open(os.path.join(os.path.dirname(__file__), 'data.bin'), 'r'), 1000000)


One caveat: To load more than 10MB of data, you will have to split the database into multiple files to work around AppEngine's size limit of static files.

Sunday, March 6, 2011

Book Notes: Pragmatic Thinking and Learning

In his book Pragmatic Thinking and Learning: Refactor Your Wetware, Andy Hunt explores interesting aspects of how human brain works, and more importantly, how we can rewire our "wetware" to be more effective learners.


Tip 1. Always consider the context.

Nothing exists in isolation.


Five stages on the journey from novice to expert:
  • Novices, who need fixed rules to follow.
  • Advanced beginners, who can try new tasks on their own but have no holistic understanding yet.
  • Competent, who can solve novel problems and apply advice from experts.
  • Proficient, who can evaluate their past performance and self-correct.
  • Expert, who can tap into a vast body of experience and work from intuition.

Tip 2. Use rules for novices, intuition for experts.


Tip 3. Know what you don't know.



Deliberate practice requires four conditions:
  • You need a well-defined task.
  • The task needs to be challenging but doable.
  • The environment needs to supply informative feedback.
  • It should also provide opportunities for repetition and correction of errors.

Tip 4. Learn by watching and imitating.

  • Imitate
  • Assimilate
  • Innovate

Tip 5. Keep practicing in order to remain expert.


Tip 6. Avoid formal methods if you need creativity, intuition, or inventiveness.


Tip 7. Learn the skill of learning.

Understanding skills acquisition is a skill itself.


Your brain has two modes (commonly known as left-brain and right-brain thinking):
  • L-mode (linear processing mode) is critical for sequential reasoning and problem solving.
  • R-mode (asynchronous, holistic, rich mode) is responsible for intuition and creativity.

Tip 8. Capture all ideas to get more of them.

Take advantage of external, preferably digital information organizers.

Tip 9. Learn by synthesis as well as by analysis.


Tip 10. Strive for good design; It really works better.

Creativity comes from the selection and assembly of the right components in the right presentation in the right context.

Tip 11. Rewire your brain with belief and constant practice.

Just thinking that your brain has more capacity for learning makes it so.

Tip 12. Add sensory experience to engage more of your brain.


Tip 13. Lead with R-mode; follow with L-mode.


Tip 14. Use metaphor as the meeting place between R-mode and L-mode.


Tip 15. Cultivate humor to build stronger metaphors.



The Morning Pages Technique for writers:
  • Write your morning pages first thing in the morning.
  • Write at least three pages.
  • Do not censor what your write.
  • Do not skip a day.

Tip 16. Step away from the keyboard to solve hard problems.

Yoga, meditation, breathing techniques, and martial arts all affect how your brain processes information.

Tip 17. Change your viewpoint to solve the problem.



Common cognitive biases to be aware of:
  • Anchoring
  • Fundamental attribution error
  • Self-serving bias
  • Need for closure
  • Confirmation bias
  • Exposure effect
  • Hawthorne effect
  • False memory
  • Symbolic reduction fallacy
  • Nominal fallacy
  • Confusion of correlation and causation

Tip 18. Watch the outliers; "rarely" doesn't mean "never".


Tip 19. Be comfortable with uncertainty.


Tip 20. Trust ink over memory; every mental read is a write.


Tip 21. Hedge your bets with diversity (of thinking to keep from falling victim to your generation's particular set of biases).


Tip 22. Allow for different bugs in different people.

Don't try to change other people's temperament to match your own.

Tip 23. Act like you've evolved; breathe, don't hiss.

Let your lizard reaction pass. Control your emotions.

Tip 24. Trust intuition, but verify.


Tip 25. Create SMART objectives to reach your goals.

SMART objectives are:
  • S - Specific
  • M - Measurable
  • A - Achievable
  • R - Relevant
  • T - Time-boxed

Tip 26. Plan your investment in learning deliberately.


Tip 27. Discover how you learn best (by experimenting with different learning modes).

Myers-Briggs types are not destiny. You can always choose to act differently.

Tip 28. Form study groups to learn and teach.


Tip 29. Read deliberately.

  • Survey the book in question to get a good overview without delving into any details.
  • Write down questions you want answered.
  • Read the book in its entirety; Recite, recall, rephrase, and reread important bits.
  • Finally review the material; Take notes and maybe draw mind maps to help visualization of information.

Tip 30. Take notes.


Tip 31. Write on: documenting is more important than documentation.


Tip 32. See it. Do it. Teach it.

Teaching forces you to constantly retrieve information which is critical for learning.

Tip 33. Play more in order to learn more.


Tip 34. Learn from similarities; unlearn from differences.


Tip 35. Explore, invent, and apply in your environment.


Tip 36. See without judging and then act.

Cultivate nonjudgmental awareness; don't try to get it right the first time, but notice when it goes wrong.

Tip 37. Give yourself permission to fail; It's the path to success.


Tip 38. Groove your mind for success.

Create mental conditions that you'd experience once you learn to perform at a higher level.

Tip 39. Learn to pay attention.

Learn the basics of meditation to more efficiently allocate your limited "attentional resources".

Tip 40. Make thinking time.

It takes time to marinate ideas. Sitting around doing nothing is part of the creative process.

Tip 41. Use a wiki to manage information and knowledge.


Tip 42. Establish rules of engagement to manage interruptions.

Avoid distractions; reduce context switching cost.

Tip 43. Send less email, and you'll receive less email.


Tip 44. Choose your own tempo for an email conversation.


Tip 45. Mask interrupts to maintain focus.


Tip 46. Use multiple monitors to avoid context switching.


Tip 47. Optimize your personal workflow.



Change is hard. Suggestions to help you manage effective change:
  • Start with a plan.
  • Avoid inaction.
  • Take time to develop new habits.
  • Belief is real. You have to believe that change is possible.
  • Take small, next steps. Choose a small, achievable goal, and reward yourself for reaching it. Rinse and repeat.

Tip 48. Grab the wheel. You can't steer on autopilot.

You need to constantly reevaluate yourself and your condition.

Reading Pragmatic Thinking and Learning: Refactor Your Wetware didn't reshape my thinking habits overnight, but it definitely helped me develop a higher level of consciousness of my state of mind.

Monday, January 31, 2011

Book Notes: High Performance Web Sites

In his 137-page book High Performance Web Sites: Essential Knowledge for Front-End Engineers, Steve Souders (who works at Google on web performance) presents 14 web site optimization rules supported by examples and code snippets.

Rule 1: Make Fewer HTTP Requests

  • Use CSS Sprites (or the less flexible image maps).
  • Use the data: URL scheme (usually for inlining images but applicable anywhere a URL is specified, including the SCRIPT tag.)
  • Merge JavaScript; merge CSS files. Use a build system to do it automatically.

Rule 2: Use a Content Delivery Network

Use CDN to host static content.
  • Pros: improved response time, backup service, high storage capacity, better caching, resilient to traffic spikes.
  • Cons: affected by other CDN clients, indirect control of content servers, subject to the performance of CDN.

Rule 3: Add an Expires Header

  • Set a far future Expires HTTP header.
    (e.g. Expires: Tue, 19 Jan 2037 00:00:00 GMT)
  • Set a Cache-Control header.
    (e.g. Cache-Control: max-age=315360000)
  • Change links when resources change. Embed file revision number or fingerprint in the URL to bust the browser cache.

Rule 4: Gzip Components

  • Turn on gzip for highly compressible content such as HTML, JavaScript, and CSS.
  • Use mod_gzip for Apache 1.3 and mod_deflate for Apache 2.x.

Rule 5: Put Stylesheets at the Top

  • Put CSS in the document HEAD using the LINK tag.
    (e.g. <link rel="stylesheet" href="style.css"/>)

Rule 6: Put Scripts at the Bottom

  • Put SCRIPTs to the bottom of the page so that they don't block rendering and parallel downloads of other resources.

Rule 7: Avoid CSS Expressions

  • CSS expressions are generally slow and dangerous. (They are also deprecated in IE8.) Do not use them.

Rule 8: Make JavaScript and CSS External

  • Put large, reusable JavaScript and CSS in external files.

Rule 9: Reduce DNS Lookups

  • Reuse connections by setting Connection: Keep-Alive in the header.
  • Use fewer domains to reduce DNS lookups.

Rule 10: Minify JavaScript


Rule 11: Avoid Redirects

  • Avoid redirecting URL just because it's missing a trailing slash.
  • Not mentioned in the book, but it's better to serve both desktop and mobile versions of a page from the same URL.

Rule 12: Remove Duplicate Scripts

  • Make sure scripts are included only once.

Rule 13: Configure ETags

  • Either turn off ETags or generate ETags that uniquely identify a specific version of a resource. The default ETag formats of popular web servers are not cache-friendly.

Rule 14: Make Ajax Cacheable

  • Make Ajax response cacheable by following rule 3, 4, 9, 10, 11, 13.

High Performance Web Sites is short and easily digestible. It's a pertinent book on speed optimization for web developers, although professional web frontend engineers may find it short of original ideas they are not already aware of.

Friday, January 28, 2011

WordGap AdWords experiment

Over the last seven days, I ran a shoestring-budget ad campaign for WordGap to get a feel of AdWords. I set a daily budget of $3, targeting at North American users across all networks and devices; twenty six search keywords related to Scrabble and anagrams were chosen, each with a default bid of $0.25.

During the one week ad campaign, 154 clicks were logged by AdWords as opposed to 283 clicks reported by Google Analytics and 285 by Google AppEngine. I can't really tell if this is normal, but the discrepancy may be explained by AdWords's removal of click spams or accidental clicks.


As you can see in the following screenshot, search ads are about an order of magnitude more effective than display ads in terms of clickthrough rate (CTR). Their average cost per click, however, turn out to be curiously close.


Now that the ad campaign has ended, I'm going to monitor the number of returning visitors for a while before running more experiments.