Re: Ruby on Neko ?

Christian Neukirchen wrote:
> Mathieu Bouchard <[e-mail]> writes:
> 
> 
>>On Sun, 20 Nov 2005, Christian Neukirchen wrote:
>>
>>>>a language and have a compiler do one big part of the job for
>>>>you. This way, even advanced features can be encoded as Neko
>>>>expressions which will then be compiled.
>>>
>>>Show how will one map singleton methods, runtime method definitions
>>>and other means of reflection to Neko?
>>
>>I'd be also interested in hearing an explanation for this:
>>
>>  "Objects are some kind of optimized hashtables. All fields names are
>>  hashed into an integer value that is used as the key into a lookup
>>  table. Insertion of a new field is O(n), access to a field is O(log n)."
>>
>>How is that optimised compared to hashtables? By definition, a hashtable,
>>when it's big enough for its number of entries, is O(1) for insertion and
>>write and read. For example, Ruby's st.c implements the hashtables used 
>>for storing @-variables, and it's all O(1). How does Neko improve on this?
> 
> 
> It is O(0), of course!!1!

It's actually O(-1), so everytime you're accessing a field you're making 
a quantum leap a few CPU cycles before.

More seriously, there is currently two implementations of objects tables 
in Neko. One is binary balanced tree that provide an amortized O(n) 
insertion but has always an O(log n) access even in the worst case. The 
other one is an flat representation of the tree as an array where it use 
dichotomy to find the corresponding field.

It also have an amortized O(n) insertion since at some time the array 
might need to grow (you could state it's O(1) if the array is big 
enough) and O(log n) access. Compared to the balanced tree, it's a lot 
more compact representation since no cells are allocated and that makes 
the GC a lot more happy.

Looking at Ruby implementation, every object needs to allocate a fairly 
big hashtable (11 buckets by default) in order to get a real O(1) access 
in practice - which can be O(n) in the worst case - and that cost (a) 
memory and (b) GC cycles when scanning it.

When Neko for example is running into Apache, that's several hundreds of 
process having all theses living objects so in that case you're more 
often memory-bound than CPU-bound, it then makes sense to trade CPU for 
memory.

It's possible that Neko object tables might be improved, I'm open to 
suggestions, but in the end I think it's always a balance between memory 
size and fragmentation (which is also very important) and CPU.

You can have a look at neko/vm/objtable.c for implementation details.

Nicolas