I've been out of the epic loop for quite a while, but I do have a few questions.
In big O notation, how does Judy compare to alists and doubly linked lists? How would the use of Judy effect scripts? I would guess that it would make all variable lookups, inserts and deletes faster. Also, what functions that scripts call would be faster using Judy? Would Judy be an improvement over Karll's arrays? The LGPL shouldn't be a problem, should it? We should be able to just link to Judy. I would think that it could start out as an optional library to use if it is installed. If it is not installed we can just fall back to alists. Of course it would be nice if we didn't have to maintain both alists and Judy. Would it be possible to include a stripped down version with it's own LGPL license inside the epic distribution? -- RoboHak Jeremy Nelson wrote: >> On Wed, Aug 09, 2006 at 06:56:09PM -0500, Jeremy Nelson wrote: >>> Judy Arrays is a modern associative array data structure. >>> http://judy.sourceforge.net/ They could be used as a >>> drop-in replacement for alists, which are unpopular with >>> some people because of the slow insert and delete times. >>> >>> Pro: There is no beating judy for performance > >> As I found from sources, Associated Lists is used for this: >> - crypt list >> - ignore list >> - logfiles list >> - window list >> (Though, I may be missing something) >> >> Jeremy, do you think that replacing alists with Jlists will >> give EPIC better performance? [...] > > The "add_to_list" function which you looked for is the doubly-linked-list [2] > handler, and this would not be affected by judy arrays, those things above > would continue to be done in doubly linked lists. > > The "add_to_array" function is the alist api, and is used for: > - Symbols (aliases, assigns, commands, functions, sets, and inline expandos) > - Nicknames on channels > - Notify > - 005 values the server supports > > I think the big question is whether or not these things are important > enough to optimize with a better data structure. [1] > > Jeremy > > [1] Alists have O(log2 N) lookups, O(N) inserts and deletes, and > O(1) sorted-order traversal. > [2] Doubly linked lists have O(N) lookups, O(N) inserts and deletes, > and O(1) sorted-order-traversal. > > _______________________________________________ > List mailing list > List@epicsol.org > http://epicsol.org/mailman/listinfo/list _______________________________________________ List mailing list List@epicsol.org http://epicsol.org/mailman/listinfo/list
