tag:blogger.com,1999:blog-3971202189709462152.post4096950404745375390..comments2024-03-11T12:50:02.036+01:00Comments on PyPy Status Blog: Faster, more memory efficient and more ordered dictionaries on PyPyCarl Friedrich Bolz-Tereickhttp://www.blogger.com/profile/00518922641059511014noreply@blogger.comBlogger18125tag:blogger.com,1999:blog-3971202189709462152.post-25621217596791243602018-02-06T22:08:05.515+01:002018-02-06T22:08:05.515+01:00The actual items are stored in a list which, like ...The actual items are stored in a list which, like a list object, is slightly overallocated. Maybe the text in the blog post missed that and it should add a "k": the average is "100 * 12/7 + 3 * WORD * 100 * k" for an average value of k around 17/16. That's around 2700 instead of 2600.Armin Rigohttps://www.blogger.com/profile/06300515270104686574noreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-92103204433848743322018-02-06T21:31:52.782+01:002018-02-06T21:31:52.782+01:00You say for 100 elements, the new design's com...You say for 100 elements, the new design's compact array uses 3 * WORD * 100 memory, right? So no extra capacity whatsoever? Then what do you do when I insert another element? Allocate a new array with 3 * WORD * 101 memory and copy all data there (and write the new element at the end)? That would be highly inefficient. So I don't believe you're honest about the memory usage.Unknownhttps://www.blogger.com/profile/13674755880850788073noreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-35703026231970124952015-02-11T10:07:10.975+01:002015-02-11T10:07:10.975+01:00@Alhabshi3k: indeed, you're right in that &quo...@Alhabshi3k: indeed, you're right in that "defaultdict" could be replaced with an alternate constructor of the regular dicts. I'm not sure why it is not so. For deques, it is maybe a question of performance, but particularly of underlying C-level memory layout: CPython can't easily add appendleft() and popleft() to regular lists while still keeping the same C API, notably PyList_GET_ITEM() and PySequence_Fast_ITEMS() --- though that is debatable.<br /><br />We could support that in PyPy, but that is arguably more of a language change than just making dicts ordered with no new user-visible API.Armin Rigohttps://www.blogger.com/profile/06300515270104686574noreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-44033990743846551462015-02-11T09:44:50.362+01:002015-02-11T09:44:50.362+01:00Thank you for improving pypy performance and featu...Thank you for improving pypy performance and features. Your project and method is promising in improvement weakness aspect of dynamic languages. At the same time, pypy should provide an simplicity of Python rather than diversity , where diversity is the reality but simplicity is the case. <br /><br />Making dictionaries ordered by default is part of simplicity; in this effort I wish integrating the features of "defaultdict" as method and properties of the the default basic dictionary. <br /><br />similar case , integrating "deque" features (as well ,method and properties) as part of pypy list datatype. <br /><br />Usually I wonder why python team didn't integrate the features of these "collections" ( as they say "High-performance container datatypes" ) within original python basic datatype, as we all know , everything in Python is an Object. and I don't think it is a pythonic way to do things in diversity.<br /><br />Anyhow , keep on your development and team spirit.Alhabshi3khttps://www.blogger.com/profile/07425990441427989165noreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-37540727205817705562015-02-05T16:11:39.987+01:002015-02-05T16:11:39.987+01:00@Durtin: there are certainly slow-downs in some ca...@Durtin: there are certainly slow-downs in some cases. If the dictionary is cold, then indeed there is one extra cache miss. It seems to be quickly compensated, though, by the fact that if then you do a few more accesses to the same dict, you are likely to get less cache misses, simply because of the more compact layout. Also, the index array is often single bytes, so it can be fully in the cache very quickly.Armin Rigohttps://www.blogger.com/profile/06300515270104686574noreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-73253618727960820652015-02-05T00:05:53.964+01:002015-02-05T00:05:53.964+01:00Just curious, was there no slowdown from adding th...Just curious, was there no slowdown from adding this extra level of indirection? For the case of accessing a random key from a cold dictionary, won't the lookup incur 2 cache misses now (one on each array), compared to just 1 for the original design?Dustin Boswellhttp://dustwell.comnoreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-43991410627844587752015-01-28T22:39:24.282+01:002015-01-28T22:39:24.282+01:00Ah indeed. I am thinking of implementing this in C...Ah indeed. I am thinking of implementing this in C++ which has coloured my thoughts somewhat. In my case, key equality checks are for the most part cheap. Thus the size/compute tradeoffs may be a bit different.<br /><br />Thanks for your thoughts.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-78011122248450801112015-01-28T17:03:22.807+01:002015-01-28T17:03:22.807+01:00@Anonymous: about starting at 16-bit instead of 8-...@Anonymous: about starting at 16-bit instead of 8-bit: it doesn't give any benefit, because rehashing is needed anyway to grow the sparse table. As long as its size is at most 256, then there is no point in storing 16-bit numbers instead of 8-bit numbers. In theory we could store N-bit numbers for the optimal value of N (= 4, 6, 8, 10...) and pay only the cost of additional complexity for individual reads and writes, not for rehashing.Armin Rigohttps://www.blogger.com/profile/06300515270104686574noreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-49324814080822876372015-01-28T13:04:38.259+01:002015-01-28T13:04:38.259+01:00two problems with that:
- since the hash function...two problems with that:<br /><br />- since the hash functions can be written in python, recomputing a hash from a key is potentially expensive<br /><br />- why would you want to throw away bits from the hash? comparing the full hashes as a first check to see whether equality has a chance to succeed is very useful. the equality function can again be written in python, so is potentially very slow.Carl Friedrich Bolz-Tereickhttps://www.blogger.com/profile/00518922641059511014noreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-38539811070610157512015-01-28T12:45:12.739+01:002015-01-28T12:45:12.739+01:00@carl - ah I see, thats interesting.
Well then, w...@carl - ah I see, thats interesting.<br /><br />Well then, what about storing the hashes with the indices?<br />* Another chunk of memory saved. Only the lowest N bits need be stored that way instead of the full 64 bits. (Big assumption that rehashing on bit size change is ok)<br /><br />* The nice thing is that the dense part (cache miss!) need only be accessed if the hash matches.<br /><br />I think if I was doing this, I'd skip 8 bit indices and have 16 bit minimum so rehashing would be very rare.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-69336953466527860312015-01-28T12:13:49.818+01:002015-01-28T12:13:49.818+01:00@Anonymous: The old approach didn't use linear...@Anonymous: The old approach didn't use linear probing either, so in that regard nothing changed.Carl Friedrich Bolz-Tereickhttps://www.blogger.com/profile/00518922641059511014noreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-52582665630195980922015-01-28T12:09:56.455+01:002015-01-28T12:09:56.455+01:00There are lots of things to like about this approa...There are lots of things to like about this approach!<br /><br />Did you find any problems with cache misses? With linear probing, the keys are accessed sequentially (cache friendly), but with this method the keys are accessed in random order.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-78468310966879097962015-01-25T07:58:21.880+01:002015-01-25T07:58:21.880+01:00JSZ: the array gets holes. If a lot of items are ...JSZ: the array gets holes. If a lot of items are deleted it can no longer be called "compact", but if it becomes too sparse it is recompacted and rehashed.Armin Rigohttps://www.blogger.com/profile/06300515270104686574noreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-11204758955147439742015-01-24T20:04:43.047+01:002015-01-24T20:04:43.047+01:00How is deleting an element implemented? It sounds ...How is deleting an element implemented? It sounds like it would take O(n) work to remove an element from the middle of the compact array.JSZhttps://www.blogger.com/profile/14689108259534709965noreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-74988044287624408262015-01-24T00:20:31.634+01:002015-01-24T00:20:31.634+01:00Awesome work and thanks. Pypy would be ahead of th...Awesome work and thanks. Pypy would be ahead of the game if PEP 468 were accepted.EM Lazzarinnoreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-43736737969383029002015-01-23T02:35:35.446+01:002015-01-23T02:35:35.446+01:00Wilfred - With the ordered dict changes that bulle...Wilfred - With the ordered dict changes that bullet item is no longer true.John M. Camarahttps://www.blogger.com/profile/14679717457363068339noreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-43209214195165096072015-01-22T17:41:50.157+01:002015-01-22T17:41:50.157+01:00Fantastic!
http://pypy.org/performance.html state...Fantastic!<br /><br />http://pypy.org/performance.html states that large dicts are a weakness of pypy -- is still the case overall, or is this work sufficient to favour pypy over cpython for large dict work in general?Wilfred Hugheshttps://www.blogger.com/profile/04515407311557751650noreply@blogger.comtag:blogger.com,1999:blog-3971202189709462152.post-18918364198773027252015-01-22T17:26:28.423+01:002015-01-22T17:26:28.423+01:00This is outstanding work, PyPy team. Keep on keepi...This is outstanding work, PyPy team. Keep on keeping on!Anonymoushttps://www.blogger.com/profile/12213846259857624016noreply@blogger.com