I just browsed a couple of old sweetcode.org articles and stumbled onto the "Judy functions" located at http://judy.sourceforge.net/.
Snippet from sweetcode.org's description: "Judy is an implementation of a sorted associative array in C. All reasonable associative array implementations have O(log N) insert and lookup complexity, but the constant factor for Judy is very much smaller than other widely used implementations (several times faster than STL's "map" and twice as fast as SGI's "hash_map", in my trivial benchmarks)."
This made me think of how beneficial it would be to Pike.
There is a lot of doc's at the site, man pages, pdf-documents with both brief and in-depth descriptions and analysis.
On associative arrays: http://judy.sourceforge.net/application/judysl.pdf
On scalable hashing: http://judy.sourceforge.net/application/Judy_hashing.pdf
On Fri, May 14, 2004 at 03:40:05PM +0200, Sten (Android) Eriksson (of Borg) @ Pike (-) developers forum wrote:
I just browsed a couple of old sweetcode.org articles and stumbled onto the "Judy functions" located at http://judy.sourceforge.net/.
Looks interesting, but it would be nice to make some benchmarks.
AFAIK, Pike code is heavily optimized too... But there is one problem with Judy (should be easily fixable, though) - it expects only null-terminated strings as indexes (JudySL), which is very serious limitation...
Regards, /Al
Well, make an object oriented Pike glue?
All Pike strings are nil-terminated, so you only have to limit to 8-bit strings only and let programmers who have nil inside the string shoot themselves in the feet.
/ Mirar
Previous text:
2004-05-14 18:06: Subject: Re: What about Judy
On Fri, May 14, 2004 at 03:40:05PM +0200, Sten (Android) Eriksson (of Borg) @ Pike (-) developers forum wrote:
I just browsed a couple of old sweetcode.org articles and stumbled onto the "Judy functions" located at http://judy.sourceforge.net/.
Looks interesting, but it would be nice to make some benchmarks.
AFAIK, Pike code is heavily optimized too... But there is one problem with Judy (should be easily fixable, though) - it expects only null-terminated strings as indexes (JudySL), which is very serious limitation...
Regards, /Al
/ Brevbäraren
Not really useful if you want to replace algorithms for basic Pike types.
/ Martin Nilsson (räfsfiskal)
Previous text:
2004-05-16 19:24: Subject: Re: What about Judy
Well, make an object oriented Pike glue?
All Pike strings are nil-terminated, so you only have to limit to 8-bit strings only and let programmers who have nil inside the string shoot themselves in the feet.
/ Mirar
In the last episode (May 16), Martin Nilsson (rfsfiskal) @ Pike (-) developers forum said:
Not really useful if you want to replace algorithms for basic Pike types.
Would simply null-escaping the key before passing it to Judy be enough? I'm not really sure what the hash value in the current mapping code is, and whether you'd use that or something else if using Judy.
No algorithm that processes strings in Pike should care about null characters. Not because it would mess up data (which it would), but because the implication is that it would use O(n) methods to find the end of the string. We have the length as an integer. Use it.
/ Martin Nilsson (räfsfiskal)
Previous text:
2004-05-17 03:00: Subject: Re: What about Judy
In the last episode (May 16), Martin Nilsson (rfsfiskal) @ Pike (-) developers forum said:
Not really useful if you want to replace algorithms for basic Pike types.
Would simply null-escaping the key before passing it to Judy be enough? I'm not really sure what the hash value in the current mapping code is, and whether you'd use that or something else if using Judy.
-- Dan Nelson dnelson@allantgroup.com
/ Brevbäraren
pike-devel@lists.lysator.liu.se
-
Alexander Demenshin -
Dan Nelson -
Martin Nilsson (r�fsfiskal) ＠ Pike (-) developers forum -
Mirar ＠ Pike developers forum
-
Sten (Android) Eriksson (of Borg) ＠ Pike (-) developers forum