On Fri, Jul 14, 2017 at 2:26 AM, Steve D'Aprano <steve+pyt...@pearwood.info> wrote: > On Fri, 14 Jul 2017 01:09 am, Rustom Mody wrote: > >> Couple that with the fact that space-time are not unrelated on any modern VM >> based OS + cache based hw. Doubly so for "managed" languages where gc buys >> space for time. > > I don't understand that comment. Space/time have *never* been unrelated. > > Trading off space for time (you can save memory by doing extra work, which > takes > time, or save time by using more memory) is an old, old trick. It applies to > 1950s mainframes just as much as 2010s smart phones, and everything in > between. > It isn't even specific to computers: what do you think a book index is, except > a way to spend extra space (more pages) to save time when looking up a topic?
I think he meant the opposite correlation. Of course we know how to use space to save time, and vice versa - anyone who's tried to organize a RL bookshelf knows that - but thanks to CPU cache lines and such, the inverse correlation is very true too. (Not that it was ever completely false.) That's why, for instance, an ASCII-only string can be processed faster in Python 3.3 than in 3.2 (and yes, I know that citing this example is going to bring a certain someone out of lurking, but I don't care - it's a great example anyway). Comparing two strings for equality, assuming that they're distinct string objects, requires scanning them for a difference. If they take up half as much space, you can do the scan in less time. The upshot is that wasting space MAY slow your program down, or conversely that a more compact data structure MAY improve performance. We're getting some similar research now with the new compact dict representation. However, this is referring to *compactness*, which is not the same thing as the size of the object. Wasted space at the end of an array of pointers (as in the CPython list implementation's spare capacity) is unlikely to make a difference. But it's a question of performance, so don't trust your gut feeling (or mine) - measure it. There are a million and one considerations, including the use of free lists, the likelihood of expansion, etc, etc, etc. ChrisA -- https://mail.python.org/mailman/listinfo/python-list
