Judy Arrays

[Jeremy Nelson]

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
Pro: The judy api is not profoundly different from the alist api
Pro: Judy is stable (no signficant changes in 2 years)
Pro: I could probably make a shim and maintain both going forward

Con: Judy is LGPLd, so I can't just drop it in epic5.
Con: Which I wouldn't anyways, because Judy is bigger than epic
Con: Judy is obscure and not widely deployed
Con: Judy requires GNU Make (epic doesn't)

What do you all think?

[Daniel M. Spielman]

She cheated on me, but I guess we could be friends.

-----Original Message-----
From: Jeremy Nelson [mailto:***@acronet.net]
Sent: Wednesday, August 09, 2006 1:56 PM
To: ***@epicsol.org
Subject: [EPIC] Judy Arrays

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
Pro: The judy api is not profoundly different from the alist api
Pro: Judy is stable (no signficant changes in 2 years)
Pro: I could probably make a shim and maintain both going forward

Con: Judy is LGPLd, so I can't just drop it in epic5.
Con: Which I wouldn't anyways, because Judy is bigger than epic
Con: Judy is obscure and not widely deployed
Con: Judy requires GNU Make (epic doesn't)

What do you all think?

[Misha]

On Wed, Aug 09, 2006 at 06:56:09PM -0500, Jeremy Nelson

Post by Jeremy Nelson
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? Personally, I use 1 or 2
persons for crypto list, 0 for ignore, about 15 slots for
logfiles and 7-10 for windows. I think there will be no
*noticeable* performance jump, probably only if one script a
benchmark. And also I think that no one use EPIC with huge
amount of above-listed things, therefor there will be no
advantage :-(

Am I wrong somewhere?

[Jeremy Nelson]

Post by Misha

Post by Jeremy Nelson
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

- 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.

[Kevin L. Mitchell]

Post by Jeremy Nelson
- 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]

And I think I should point out my Database Primitives (dbprim) library,
which I originally wrote for replacing ircu's database. It includes
doubly-linked lists, hash tables, sparse matrices (for managing
user-on-channel associations and the like), and red-black trees (for
cases where you need efficient searching and ordered display)...take a
look at http://www.sourceforge.net/projects/dbprim/

[RoboHak]

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

Post by Jeremy Nelson

Post by Misha

Post by Jeremy Nelson
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

- 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.
- 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
http://epicsol.org/mailman/listinfo/list