3

Alist and plist are very similar structures -- an alist with suitable functions can implement major features that plist provides: read/modify an existing key-value pair; write a new pair.

If you’re good at Algorithm, you’ll find that alist and plist are nearly equivalent in practice:

  • the time complexity of accessor-functions for alist is the same as the one for plist;
  • in terms of storage, alist and plist have exactly the same space complexity.

But there’re still some differences:

  • the print representation of alist is more human-readable.
  • it’s faster to count alist’s number of key-value pairs.

Now let’s get down to business. GNU Emacs Lisp Reference Manual, 5.9.1 Property Lists and Association Lists:

Property lists are better than association lists for attaching information to various Lisp function names or variables.

If your program keeps all such information in one association list, it will typically need to search that entire list each time it checks for an association for a particular Lisp function name or variable, which could be slow.

If you keep the same information in the property lists, each search will scan only the length of one property list, which is usually short.

Why does the manual state such these reasons why ELisp chooses plist for attaching information? These reasons seem to be wrong.


Some facts that may be helpful:

Plist doesn't use less memory: to store a new key-value pair, both alist and plist need 2 conses:

+-------+   +---+  +-------+
|new key|   | *----+new key|
+-------+   +-+-+  +-------+
|   *   |   | * |  |new val|
+---|---+   +-|-+  +-------+
    |         |
+---+---+    the
|new val|  original
+-------+   alist
|   *   |
+---|---+
    |
   the
 original
  plist

The access (e.g., to find a value by key) performance is the same: please prove it yourself.

3
  • emacs.stackexchange.com/tags/elisp/info
    – Drew
    Commented Feb 4, 2023 at 15:09
  • The question is too broad and encourages opinion-based answers, so it should be closed. Please split it up into separate question posts, for some of the specific questions you asked. Ask very specific questions: Can I do XYZ with alist/plist? What's the performance difference between doing XYZ with plist or alist? etc. Thx.
    – Drew
    Commented Feb 4, 2023 at 15:15
  • @Drew: I've edited it; hope this is not a bad question. |||| "Ask very specific questions: Can I do XYZ with alist/plist?" -- I don't want to know what I can do with them (because I can call shortdoc-display-group myself). I post this question for curiosity instead of practical use.
    – shynur
    Commented Jul 5, 2023 at 5:12

2 Answers 2

2

I think the key is the sentence "If your program keeps all such information in one association list, it will typically need to search that entire list each time it checks for an association for a particular Lisp function name or variable, which could be slow." (emphasis added). E.g. you could implement symbol properties by having an alist with symbols being the keys and the property list being the value. Looking up a property involves a lookup in the (potentially very long) list to get the entry and then a (presumably short) lookup in the entry value for the property. Having the plist associated directly with the symbol, allows you to bypass the long search and just do the short lookup. You still need to find the symbol (presumably in the oblist/obarray), but that is presumably a hash search rather than a linear search.

I could be wrong (which is the reason for all the "presumably" weasel words) but that's how I read it.

3
  • Sorry, seems that my question description has misled you: “Having the plist associated directly with the symbol” -- What I asked is Having the alist associated directly with the symbol; one alist serves only one symbol.
    – shynur
    Commented Jul 6, 2023 at 1:21
  • That's exactly my point: I don't think that's what they are describing.
    – NickD
    Commented Jul 6, 2023 at 1:27
  • Ah, I got what you mean. Perhaps that is the case. Although I don't think it's necessary to say why “having an alist with symbols being the keys and the property list being the value” is slower, because it's obvious.
    – shynur
    Commented Jul 6, 2023 at 1:39
0

Not an answer, but just a note about duplicate keys:

If one symbol’s plist could have the same property names (like alist), it may also be faster for plist to update its content. Why not do that?

put doesn't do it, but in principle there's nothing stopping you putting duplicate keys into a plist:

(plist-get '(:foo bar1 :foo bar2) :foo)
=> bar1

Doing that would then be a trade-off between memory (using more of it) and access speed (maybe making some things faster to access -- potentially also making other things slower to access by side-effect, if you now need to traverse a heap of duplicate keys to reach other values).

You have the exact same decision to make when using alists -- you can find an existing item and update that in place, or you can just push new items to the front of the list. Which approach makes best sense can vary from one program to another.

For general-purpose symbol properties, I presume the more conservative approach was considered preferable.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.