search

kevinlawler / kona

Open-source implementation of the K programming language
ISC License
1.36k stars 138 forks source link

optimized dictionaries #112

Open kevinlawler opened 13 years ago

kevinlawler commented 13 years ago

The current dictionary implementation offers lookup in time O(n) in the number of keys. Create a new implementation with O(1) time lookup.

silentbicycle commented 13 years ago

Any algorithm preference? Is there any code dependent on the dictionary internals that wouldn't be obvious? I know streaming & reading will also be affected...

kevinlawler commented 13 years ago

Is there any code dependent on the dictionary internals that wouldn't be obvious?

Dictionary code is spread throughout the codebase. There will be a sizable list of places in the code that will need to be touched. Several non-obvious places I can think will cause problems: amend, .k.a.b.c style lookup (& the core dictionary functions), some code in parse that's dependent on the implementation. Now that I think about it the wd() style execution may be heavily dependent on the implementation.

Any algorithm preference?

It might be worth supporting pluggable methods through some API-like system. Doesn't seem like much overhead to do that. If I pick the algorithms they will be reliant though predictably boring.

silentbicycle commented 13 years ago

That's what I figured. I will meditate on it.

silentbicycle commented 13 years ago

The verb dispatch table has a DICT tag to note where dictionary changes would be necessary. Moving the dict code into its own file with an abstract interface will help with benchmarking multiple implementations.

silentbicycle commented 11 years ago

It would indeed involve a LOT of changes throughout the codebase.

I think some kind of dynamically resized, internally-chained hash table would be a good fit - fewer allocations, in large slabs, seems to fit K's DNA. That or B-Trees. Fortunately, symbols are both hashable and ordered.