Using Lisp (or AutoLisp) how good is the associative lists performance?

Question

I'm doing an AutoLisp project which uses long associative structures to do heavy geometrical processing - so I'm curious about the associative list intense use timing results. How simple/complex is the implementation? It uses some data structure or a normal list of dotted pairs? The are any extension for b-tree or something?

Answer 1

In Common Lisp and Emacs Lisp association lists are linked lists, so they have linear search time. Assuming that AutoLisp is the same (and if it isn't, then their use of the term "Associative List" is misleading), you can assume that all operations will be linear in the length of the list. For example, an alist with 100 elements will, on average, need 50 accesses to find the thing that you are after.

Answer 2

Of course, most Scheme implementations (or maybe it's in the specs?) have hashtables, which use mostly the same API; but it's not transparent, when you ask for an alist, you get a list of pairs, if you want a hashtable, ask for it.

that said, it's important to remember that linear algorithms aren't slow; they're 'unscalable'. for a small number of elements, they'll outperform a more complex 'clever' algorithm. just how large 'n' has to be, depends a lot on the algorithm, and fast processors with big caches but slow RAM, keep pushing it. Also, heavy optimising compilers (like those available on some Lisp's) generate very tight linear code.

Answer 3

I have not worked with AutoLisp in about 10 years, but I never found any real performance issues with association list manipulation. And I wrote code that would do a fair amount of association list manipulation.

Working in VBA or ObjectARX might have some performance benefits, but you would probably need to run some comparison testing to see if it is really better.

Answer 4

the turning point for SBCL on recent x86 hardware between alists and identity based hashtables, assuming even distribution of access, is around 30-40 elements.

Answer 5

There is no extension for b-tree that I know of but if you use Visual LISP you can use ActiveX objects and thus access most types of databases.