Oleg Andreev

Cuckoo hashing papers

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.

Robust singletons in AS3

This is funny.

“hash-table” objects vs. message-receiving objects

(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 vs. Idea

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.

Io namespaces

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!
  )
)

MyApp := Object Module clone do(
  Foo := Object clone do(
    bar := method(Bar)
  )
  Bar := Object clone do(
    foo := method(Foo)
  )
)

Module := Object clone do(
  Object := method(self)
)

Null Pattern revisited

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.

iovm idea: “activatable” should be a slot property rather than value property. This allows to pass methods around and access them directly by slot name in all the contexts. Current implementation makes you to use getSlot(slotName) syntax to avoid activation.