Oleg Andreev
Month
A Cool And Practical Alternative To Traditional Hash Tables
More Robust Hashing: Cuckoo Hashing with a Stash
Recent advances in the theoretical literature have proposed interesting modifications to traditional hash tables. The authors of these papers propose hash tables which
a) have a guaranteed constant time for a lookup
b) have amortized constant time for an insertion
c) require table size only slightly larger than the space for the elements
Previous hash table technologies have offered at most two of these three.
(Thanks to Julik for inspiring to think on the subject.)
In Io, JavaScript and Python there’s a model of “hash-table” objects. The object contains some slots, which you access and then decide what to do with them. If the slot appears to be a function, you can call it. In JS there’s a bit of magic: interpreter knows where the function just came from, so it can specify reasonable “this” pointer for function call. In Io there’s less smart decision: upon slot access interpreter checks “activatable” property of the object (not the slot entry, but the object this slot refers to!) and activates the object if it happens to be a method. However, in Io x := y is being a message setSlot(‘x’, y), so that you can hook in.
On the other hand, Ruby has a much stronger notion of message passing: you never ever can modify inner object data (that is, @ivars) without message send. The most simple @foo update happens through the accessor method called foo=.
However, from the implementation point of view, Ruby has two kinds of hash tables per object: method table and ivars table.
Implementation is created under time and knowledge constraints. Therefore, it is full of bugs, and it becomes obsolete as soon as our knowledge evolves. What is important in technology: the idea and context behind each decision.
MyApp := Object clone do(
Foo := Object clone do(
bar := method(Bar) # Bar is not accessible from here!
)
Bar := Object clone do(
foo := method(Foo) # Foo is not accessible from here!
)
)
How can we improve that? First, lets define MyApp with Module clone rather than Object clone:
MyApp := Object Module clone do(
Foo := Object clone do(
bar := method(Bar)
)
Bar := Object clone do(
foo := method(Foo)
)
)
All we need now is to have all inner objects to have MyApp in the list of prototypes. Therefore, lets override Object slot to refer to MyApp rather than the standard Object:
Module := Object clone do(
Object := method(self)
)
See Module.io on GitHub.Yesterday I have rewritten 3600 LOC codebase in ActionScript as if there were “message eating” null in the core and the standard libraries (please see A Generalized Null Object Pattern by Nevin Pratt). I got a diff with just 100 lines removed and 180 lines updated. It is at most 7% code reduction.
It seems that “message eating” null neither produces considerably more elegant code, nor considerably more brittle code (in all cases ignoring null value is correct).
In sense of VM implementation, it might be easier to implement a classical “exception raising” null and use custom Null Pattern classes where appropriate.
Good software framework saves much more time providing explicit knowledge where to put things in, rather then providing syntactic steaks and strippers.