4 ms·

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, oth

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

by _wmd 14y ago

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.