5 ms·

Skip lists: fast PyPy-compatible ordered map in 89 lines of Python

77 points by _wmd 14y ago

paxswill 14y ago
> As many will attest, it’s easy to live life without an ordered map in Python, but the moment you need one Python starts to suck really fucking hard. This should be built into the language somehow. OrderedDict [0] was added with Python 3.1, and there's an equivalent (pure Python) class provided in the docs for backwards compatibility. Just in case the author reads this, it would make the code nicer to implement the appropriate "magic" method names that make it act like built-in containers [1]. 0: http://docs.python.org/3.3/library/collections.html?highlight=collections#collections.OrderedDict http://docs.python.org/3.3/library/collections.html?highligh... 1: http://docs.python.org/3.3/reference/datamodel.html#emulating-container-types http://docs.python.org/3.3/reference/datamodel.html#emulatin...
- _wmd 14y ago
  OrderedDict tracks insertion order, not key order. Additionally it is not possible to start iteration from an arbitrary key. The method and variable names here mostly reuse the names from the original skip lists paper, although in a real generic implementation, reusing the mapping protocol would be a nice touch. I posted this more due to the ridiculous simplicity of implementation: skip lists themselves are far more worthy of note than my horrid example code.
_wmd 14y ago
This implementation may look ghastly at first sight, however it's worth note that: * The node pointer list is reused for the node structure to save memory, otherwise a minimum of 72 bytes is wasted per node on CPython, in addition to malloc slack for 2 allocations (the list object itself, and the array of pointers). As it stands, CPython burns about 100 bytes per record, so 'clean' code here would potentially double the memory requirements in addition to added runtime cost. * Numeric, rather than symbolic indexing wins 5k lookups/second on CPython. It's debatable whether using speed hacks like "search(key, IDX_PREV=IDX_PREV, IDX_NEXT=IDX_NEXT)" is uglier than the bare numbers themselves. Using accessor functions to pretty the code also costs quite a lot.
- aidenn0 14y ago
  Out of curiousity, what made you pick skip-lists over a trie structure, such as crit-bit trees?
  - _wmd 14y ago
    Primarily because I knew from previous research that they were easy to implement. Secondarily because unlike most trees, they're amenable to concurrent update (although this is mostly irrelevant to a Python application) and I wanted to get some foundational experience. Locking a skip list is very straightforward, and slightly less intuitive lockless versions also exist.
    - mzl 14y ago
      I'm wondering if "slightly less intuitive" is a deliberate understatement or not :) I recently read through the concurrent skip list map implementation in Java that is lockless. That code is definitely quite tricky, and the comments refer to three PhD thesis's one should read to understand how it works.
- ekimekim 14y ago
  This is a conflict that I find very interesting. Python is a language very much about readability. You often find examples like this where "good code" is slower than "ugly code". I would imagine, however, that PyPy's JIT makes alot of these problems go away?
  - _wmd 14y ago
    On PyPy it should be more efficient to have a 'class Node:', where when enough instances with similar attributes exist, it'll optimize to something like CPython `__slots__`. One issue is the list of pointers on each node. This could be kept as a separate list attribute (another 2 mallocs, slack, list overallocation etc), or perhaps arranged so that "$max_levels" types exist, each with attributes to cover a particular level. In any case since I wanted CPython compatibility, the horrid list trade-off is the best I could find. You raise an interesting topic, I got into Python around the 2.2 era almost entirely due to the "cleanliness" factor, but features quickly began to appear that seemed redundant in some way, and the general popularity of the language meant its philosophy became increasingly dilute. Basically whatever "obviousness" the language had is eroded by varying degrees of pomp and ceremony, e.g. "idiomatic" use of crazy stuff like metaclasses, decorators everywhere, or nested list comprehensions containing perlish conditional expressions. It seems healthier to look at Python less as some bastion of beauty and more a slightly prettier glue language, like a perl 2.0. From this angle it becomes an interesting macro language for combining chunks of C in interesting ways. You can write some awesomely fast, concise code with abuse of buffer(), itertools and functools.partial, but none of it looks particularly "Pythonic" or "beautiful". Nonetheless the resulting code is among the best in its class in terms of performance/size/maintainability compromise, yet the community at large would likely reject it as abhorrent. I guess this code snippet is a good example of that.
btilly 14y ago
Random note. The "public domain dedication" is the wrong way to make code available for anyone to do what they want with it. The problem is that under US copyright law, you and your heirs actually own that copyright, whether you want to or not. Declaring otherwise has no legal force. Which means that if you change your mind, or if your heirs feel differently than you do, people can potentially be sued for copyright violations on that code. Unlikely, but possible. By contrast releasing your code under an extremely permissive license has legal force, and neither you nor your heirs can unrelease it. (Assuming, that is, that you own copyright to your own work. Sometimes people do not, and do not realize this...)
- _wmd 14y ago
  Thanks. I've slightly improved that paragraph, although I guess it should really be mentioned in the code itself. In any case what's worthy of note is that this can be done with so little code in the first place, rather than the ugly example I've provided
  - dmm 14y ago
    There are several MIT licenses. Just use the ISC license. It's the shortest license possible. http://en.wikipedia.org/wiki/ISC_license http://en.wikipedia.org/wiki/ISC_license
    - FrankBooth 14y ago
      With the "and distribute" or "and/or distribute" wording? Different factions have expressed preferences for each option.
      - dmm 14y ago
        I have no idea. haha ok I'll stop trying to give license advice. I do know the OpenBSD project uses "and/or distribute" on the advice of the FSF.
- tptacek 14y ago
raymondh 14y ago
FWIW, there has long been another Python skiplist recipe at: http://code.activestate.com/recipes/576930/ http://code.activestate.com/recipes/576930/ and it is indexable as well. It is under an MIT license and runs great under PyPy.
- deleted 14y ago
  [deleted]

77 points by _wmd 14y ago

> As many will attest, it’s easy to live life without an ordered map in Python, but the moment you need one Python starts to suck really fucking hard. This should be built into the language somehow. OrderedDict [0] was added with Python 3.1, and there's an equivalent (pure Python) class provided in the docs for backwards compatibility. Just in case the author reads this, it would make the code nicer to implement the appropriate "magic" method names that make it act like built-in containers [1]. 0: http://docs.python.org/3.3/library/collections.html?highlight=collections#collections.OrderedDict http://docs.python.org/3.3/library/collections.html?highligh... 1: http://docs.python.org/3.3/reference/datamodel.html#emulating-container-types http://docs.python.org/3.3/reference/datamodel.html#emulatin...

_wmd 14y ago
OrderedDict tracks insertion order, not key order. Additionally it is not possible to start iteration from an arbitrary key. The method and variable names here mostly reuse the names from the original skip lists paper, although in a real generic implementation, reusing the mapping protocol would be a nice touch. I posted this more due to the ridiculous simplicity of implementation: skip lists themselves are far more worthy of note than my horrid example code.

_wmd 14y ago

This implementation may look ghastly at first sight, however it's worth note that: * The node pointer list is reused for the node structure to save memory, otherwise a minimum of 72 bytes is wasted per node on CPython, in addition to malloc slack for 2 allocations (the list object itself, and the array of pointers). As it stands, CPython burns about 100 bytes per record, so 'clean' code here would potentially double the memory requirements in addition to added runtime cost. * Numeric, rather than symbolic indexing wins 5k lookups/second on CPython. It's debatable whether using speed hacks like "search(key, IDX_PREV=IDX_PREV, IDX_NEXT=IDX_NEXT)" is uglier than the bare numbers themselves. Using accessor functions to pretty the code also costs quite a lot.

aidenn0 14y ago
Out of curiousity, what made you pick skip-lists over a trie structure, such as crit-bit trees?
- _wmd 14y ago
  Primarily because I knew from previous research that they were easy to implement. Secondarily because unlike most trees, they're amenable to concurrent update (although this is mostly irrelevant to a Python application) and I wanted to get some foundational experience. Locking a skip list is very straightforward, and slightly less intuitive lockless versions also exist.
  - mzl 14y ago
    I'm wondering if "slightly less intuitive" is a deliberate understatement or not :) I recently read through the concurrent skip list map implementation in Java that is lockless. That code is definitely quite tricky, and the comments refer to three PhD thesis's one should read to understand how it works.
ekimekim 14y ago
This is a conflict that I find very interesting. Python is a language very much about readability. You often find examples like this where "good code" is slower than "ugly code". I would imagine, however, that PyPy's JIT makes alot of these problems go away?
- _wmd 14y ago
  On PyPy it should be more efficient to have a 'class Node:', where when enough instances with similar attributes exist, it'll optimize to something like CPython `__slots__`. One issue is the list of pointers on each node. This could be kept as a separate list attribute (another 2 mallocs, slack, list overallocation etc), or perhaps arranged so that "$max_levels" types exist, each with attributes to cover a particular level. In any case since I wanted CPython compatibility, the horrid list trade-off is the best I could find. You raise an interesting topic, I got into Python around the 2.2 era almost entirely due to the "cleanliness" factor, but features quickly began to appear that seemed redundant in some way, and the general popularity of the language meant its philosophy became increasingly dilute. Basically whatever "obviousness" the language had is eroded by varying degrees of pomp and ceremony, e.g. "idiomatic" use of crazy stuff like metaclasses, decorators everywhere, or nested list comprehensions containing perlish conditional expressions. It seems healthier to look at Python less as some bastion of beauty and more a slightly prettier glue language, like a perl 2.0. From this angle it becomes an interesting macro language for combining chunks of C in interesting ways. You can write some awesomely fast, concise code with abuse of buffer(), itertools and functools.partial, but none of it looks particularly "Pythonic" or "beautiful". Nonetheless the resulting code is among the best in its class in terms of performance/size/maintainability compromise, yet the community at large would likely reject it as abhorrent. I guess this code snippet is a good example of that.

btilly 14y ago

Random note. The "public domain dedication" is the wrong way to make code available for anyone to do what they want with it. The problem is that under US copyright law, you and your heirs actually own that copyright, whether you want to or not. Declaring otherwise has no legal force. Which means that if you change your mind, or if your heirs feel differently than you do, people can potentially be sued for copyright violations on that code. Unlikely, but possible. By contrast releasing your code under an extremely permissive license has legal force, and neither you nor your heirs can unrelease it. (Assuming, that is, that you own copyright to your own work. Sometimes people do not, and do not realize this...)

_wmd 14y ago
Thanks. I've slightly improved that paragraph, although I guess it should really be mentioned in the code itself. In any case what's worthy of note is that this can be done with so little code in the first place, rather than the ugly example I've provided
- dmm 14y ago
  There are several MIT licenses. Just use the ISC license. It's the shortest license possible. http://en.wikipedia.org/wiki/ISC_license http://en.wikipedia.org/wiki/ISC_license
  - FrankBooth 14y ago
    With the "and distribute" or "and/or distribute" wording? Different factions have expressed preferences for each option.
    - dmm 14y ago
      I have no idea. haha ok I'll stop trying to give license advice. I do know the OpenBSD project uses "and/or distribute" on the advice of the FSF.
tptacek 14y ago

raymondh 14y ago

FWIW, there has long been another Python skiplist recipe at: http://code.activestate.com/recipes/576930/ http://code.activestate.com/recipes/576930/ and it is indexable as well. It is under an MIT license and runs great under PyPy.

deleted 14y ago
[deleted]