Es/FlightGear Newsletter November 2013: Difference between revisions

== Nasal Internals for hackers: Intern'ing symbols ==

''Contributed by Philosopher''

As some of you experienced Nasal/C-code hackers should recall, or even those familiar with scripting languages internals, namespaces are just hashes, with keys representing symbols - right? Well yes, mostly, but each of those symbols are unique in a way from all of the other strings out there: they're interned. (Interning is a process that takes strings and a dictionary and returns a matching string, adding one if needed. That means equal strings are substituted so they have the same pointer, i.e. one string represents all instances of "io", stored in a pool/hash of all used symbols.) Though these interned strings appear at runtime in the keys in namespaces, they get created during code generation (codegen), where the symbols (TOK_SYMBOL) get converted to Nasal strings, are interned to get the correct string (using the globals->symbols hash), and are stored in the naCode's constants' block. From there, the symbol-strings are used to set and get various lvalues (both local/global symbols and objects' members) in an optimized way (that's the whole point of the exercise). Looking at hash.c, there are some specialized functions that make use of the potential optimizations:

* naiHash_sym (looks up an interned symbol)

* naiHash_newsym (adds a symbol in the first empty slot for the hashcode)

(There's another that looks similar, naiHash_tryset, but it does not deal with interned symbols: it uses the findkey() method, which in turn uses the equals() method that checks for more general key equality instead of simple pointer equality.)

The first, naiHash_sym, is pretty neat and the prime example of the optimization: it runs through a hashcode's potential slots, checking only pointer equality (note that interned symbols' hashcodes are computed during interning, so that's another step that doesn't have to be done are runtime). naiHash_newsym is another nice optimization but a little problematic, due to its assumption that the key doesn't exist already. It's basically used for adding another argument as a local key, but it doesn't care about if it exists already, it just sees an occupied slot and keeps going. Consider the following example that illustrates calling with an argument into a hash that already has the argument's key in it:

This should print:

This shows that the key is being set twice (which violates a normal precondition of hashes): once as an argument and once to create an existing key in the namespace. The one set first is the one being picked up (e.g. the arg in {arg:nil} versus the arg... that equals []). And this behavior persists even through resizing: hashset() (which is used to reinitialize a hash after reallocation) only keeps appending keys in empty slots, so the number of keys doesn't change (even if there are multiple of the same keys).

For this reason, I would suggest amending naiHash_newsym to check keys' pointer equality before continuing; that way symbols aren't "trodden" over like this. (Please note that if "arg" exists in the hash as non-interned, then it will be trodden over anyways; having to look for non-interned symbols would mainly violate the point of the optimization at this step, and doesn't actually matter in the long run.) I would argue that finding an existing key (a few simple pointer comparisons!) would be more efficient generally, because the hash would never need to be resized if an existing one is found, whereas the old version would append regardless. (I think I once counted well over a hundred "arg" symbols in the __js0 namespace from the continual firing of bindings, which obviously isn't good.)

Continue reading at [http://forum.flightgear.org/viewtopic.php?f=30&t=21308&p=193935#p193935].