Write this accumuator in a functional style

[Chris Angelico]

On Fri, Jul 14, 2017 at 2:26 AM, Steve D'Aprano
<steve+python at 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