The Inbox: Collections-cmm.874.mcz

Note that your statistics do not account for transient collections. If minimizing the initial capacity made most uses of these collections slower, it might not be justified to do so.

Am Fr., 24. Jan. 2020 um 23:28 Uhr schrieb Chris Muller <[hidden email]>:

Wow, the number of oversized OrderedCollection instances is much worse, 92%.

((OrderedCollection allInstances count: [ : e | e size < 10 and: [ e array size >= 10 ] ]) /
OrderedCollection allInstances size) asFloat.

On Fri, Jan 24, 2020 at 4:01 PM Chris Muller <[hidden email]> wrote:

Hi all,

In my trunk image, currently >10% of Dictionary instances have unnecessarily large internal arrays because they were created with #new but never grew.  

     ((Dictionary allInstances count: [ : e | e size < 3 and: [ e array size >= 5 ] ]) / Dictionary allInstances size) asFloat      "0.11282051282051282"

A developer wanting compactness should not be required to probe into the internal implementation to know whether they can write the most compact code, "Dictionary new" and "Set new".  The most compact code should result in the most compact size by default, and only if a *larger* default size is desired, use #new: for optimization.

This also addresses the issue I've been discussing with Levente, ensuring #new: maintains its performance optimization along with space, as with OrderedCollections, etc.

Best,

  Chris

On Fri, Jan 24, 2020 at 3:32 PM <[hidden email]> wrote:

Chris Muller uploaded a new version of Collections to project The Inbox:
http://source.squeak.org/inbox/Collections-cmm.874.mcz

==================== Summary ====================

Name: Collections-cmm.874
Author: cmm
Time: 24 January 2020, 3:32:43.628249 pm
UUID: 107f3a74-177c-4338-9ad3-648e427419a1
Ancestors: Collections-ul.871

- Optimize for system compactness by ensuring the default internal array size of any HashedCollection is not initialized larger than it may ever need to be.
- Let #new: be used to define larger sizes than the minimum, and perform comparably with #new even if the minimum size is specified.

=============== Diff against Collections-ul.871 ===============

Item was changed:
  ----- Method: HashedCollection class>>new (in category 'instance creation') -----
  new
+       ^ self basicNew initialize: 3!
-       ^ self basicNew initialize: 5!

Hi Chris,

On Fri, 24 Jan 2020, Chris Muller wrote:

> Hi Jakob,
>
> Optimal execution performance can never be assured with #new, since the potential cost of under-allocation in various places is offset by the gains of not over-allocating in other places. 
>
> Although it's impossible to tweak the default initial size in #new to optimize for performance, we can at least optimize for space, and also for clarity-of-usage.  #new, by nature, expresses a "lack of concern for optimization", so Squeak should at least provide compactness in that case.  Places in the code that
> need optimization will correctly express that by writing #new: with a larger pre-allocation.
>
> It's true that system level changes of any kind could result in the need for downstream changes but, in this case, it seems very unlikely.

The way I understand it, Jakob says that your suggested change has a
chance to slow down things just to save a few hundred kilobytes of memory.

I don't think we would want to do that without measuring the effects of
the change somehow.

Same applies to OrderedCollections.

Following your reasoning, the optimal initial capacity for any dynamic
collection created with #new should be 0, but that doesn't feel right...

>  
>       I don't think we would want to do that without measuring the effects of
>       the change somehow.
>
>
> Performance measuring is already part of every system that cares, right?   :)

Of course not. That's why "somehow" is there. I don't know how it could be
measured, but I think that without measurements, it's risky to change
something like that.

> None of those systems are depending on any particular default initial size for performance.  If they are, they should be fixed.

Here is an example scenario:
I write my code. I use [OrderedCollection new]. I see that my code is fast
enough.
You change the default capacity from 10 to 3. My code is now too slow. I
have to profile it to see why. It turns out that I store 7-9 elements most
of the time, and the capacity of 10 was a good fit, but 3 is not, because
it means growing twice (first to 6, then to 12), and my code ends up
being slower and using more memory than before.

>  
>
>       Same applies to OrderedCollections.
>
>       Following your reasoning, the optimal initial capacity for any dynamic
>       collection created with #new should be 0, but that doesn't feel right...
>
>
> Not 0, 3.  It's "reasoning", not extremism.  :)
>
> 3 would be a great default for OrderedCollection.  Ultra-minimal, but with a purpose.   I mean, really, with 10, we have 92% of all instances wasting space.

"Wasting space" is a must when you implement dynamic arrays and
hash tables. It's a space-time tradeoff[1].

Levente

[1] https://en.wikipedia.org/wiki/Space%E2%80%93time_tradeoff

Here is an example scenario:

I write my code. I use [OrderedCollection new]. I see that my code is fast
enough.
You change the default capacity from 10 to 3. My code is now too slow. I
have to profile it to see why. It turns out that I store 7-9 elements most
of the time, and the capacity of 10 was a good fit, but 3 is not, because
it means growing twice (first to 6, then to 12), and my code ends up
being slower and using more memory than before.

This example makes the case for this proposal, by showing that it was *depending on knowing the private, internal initial size*, for its performance.  By having written #new instead of #new: in performance-critical code, it was and still is less efficient than it could be.  No amount of "guessing" of an initial size will help execution performance, but could at least guarantee space efficiency.

But we should not break #new: 1 and #new: 2 for HashedCollections, please.

> You should be careful, Levente, Collections-ul.871 does it, too.  Everywhere #new: 1 or #new: 2 occurs, you've reduced the internal array size from 5 to 3.  And, yes, it did indeed introduce this unexpected anomaly!

When one says [Dictionary new: 1] or [Dictionary new: 2], one expects to
get a dictionary that can hold one or two elements, respectively.

Collections-ul.871, just like the former version, creates dictionaries
matching those expectations, but Dictionaries returned by the new version
use less memory.
So, what's the problem?

How often do you investigate the internals of classes your code uses to
avoid relying on the default values coded into them

when there are no
performance problems with your code? I guess never...

> But we should not break #new: 1 and #new: 2 for HashedCollections, please.

The performance difference between #new, and #new: X where X is <= 3,
didn't bother you (or anyone else) until recently.

I proposed all kinds of solutions to minimize the difference between #new
and #new:, and we seemed to agree on one of those.

Am Sa., 25. Jan. 2020 um 06:55 Uhr schrieb Chris Muller <[hidden email]>:

Here is an example scenario:

I write my code. I use [OrderedCollection new]. I see that my code is fast
enough.
You change the default capacity from 10 to 3. My code is now too slow. I
have to profile it to see why. It turns out that I store 7-9 elements most
of the time, and the capacity of 10 was a good fit, but 3 is not, because
it means growing twice (first to 6, then to 12), and my code ends up
being slower and using more memory than before.

This example makes the case for this proposal, by showing that it was *depending on knowing the private, internal initial size*, for its performance.  By having written #new instead of #new: in performance-critical code, it was and still is less efficient than it could be.  No amount of "guessing" of an initial size will help execution performance, but could at least guarantee space efficiency.

If you optimize the default for space instead of sticking with a reasonable tradeoff,

you might force people to use new: and think about the very implementation details of those collections to get back to reasonable results.

You might turn a piece of code into a bottleneck even though it was not considered performance-critical before.

On the other hand, who else was bothered by too sparse hashed or ordered collections until now?

Is it a problem that bothers many, in comparison to the group which the change could bother?

I suppose this is premature optimization. If people have identified compactness as a requirement,

they shall use #new: with (domain specific) expected numbers or patch #new for their application. But don't force it on everyone.

You wouldn't like me to submit a "performance optimization" that changes the new default capacity to 100 because my application happened to deal with collections of that size frequently and because memory is comparably cheap and large nowadays, would you?

We can only really know the impact if we have a benchmark or even an idea of realistic average collection usage. Maybe someone wrote a paper about that...

Hi Levente, hi Jakob,

Thanks for the interesting discussion.  I'd like you to know, I'm not gung-ho about this change, but do think we should seriously consider it for the benefit of Squeak.  I think the benefit is real, but deceptive.

It seems there are two dimensions to the decision:

  - legacy / compatibility

  - API design / user-expectations

I do respect your point about legacy, that writing #new has always meant you get something that can hold up to 10 elements before needing to grow, instead of only 3.

It "sounds" reasonable, but...

Here are some certainties:

    - Allocating a 3 element array is quicker than allocating 10 element one.

    - 3 element Array's take up less memory than 10 element ones

    - consuming more RAM can lead to slowdowns due to paging or GC overhead

    - In the worst possible case (e.g., doing it over and over and nothing else), adding 9 elements to an (OrderedCollection new: 3) is 72% the speed of adding 9 elements to an (OrderedCollection new: 10). see [1]

Here are some uncertainties:

     - there may be some code somewhere creating many thousands of OrderedCollections (if it were only a few, it wouldn't be noticed)

     - the many thousands are all created in a very short amount of time (if it were spread out over time, it wouldn't be noticed)

     - it then stores 7-9 elements in most of the OrderedCollections

     - in spite of all of the above, the author still wrote #new instead of #new:

Letting fear of such remote uncertainties dominate your decision even in light of those certainties brings paralysis.  Squeak can hardly improve if such low-risk items can't even be attempted at the beginning of a development cycle, when applications will surely undergo testing before deploying to the next version of Squeak (5.4).  Our community is small (low chance) and helpful (low impact).

___

That leaves the API discussion, which was mostly ignored, but is really the key.  I would like to touch on this with some responses, below:

 

> You should be careful, Levente, Collections-ul.871 does it, too.  Everywhere #new: 1 or #new: 2 occurs, you've reduced the internal array size from 5 to 3.  And, yes, it did indeed introduce this unexpected anomaly!

When one says [Dictionary new: 1] or [Dictionary new: 2], one expects to
get a dictionary that can hold one or two elements, respectively.

How many should one "expect" to get with #new?   Because one reason you gave for not wanting to reduce the default size seems to be based on some "expectation" you have for it.

There should be only one:  that it shouldn't be significantly faster than #new: 1.   Nothing else.

 

Collections-ul.871, just like the former version, creates dictionaries
matching those expectations, but Dictionaries returned by the new version
use less memory.
So, what's the problem?

It slowed down (Dictionary new: 1) relative to trunk, 

by a comparable margin as adding 9 elements to an (OrderedCollection new: 3) relative to an (OrderedCollection new: 10 

(see [1])

How often do you investigate the internals of classes your code uses to
avoid relying on the default values coded into them

The answer is already "never" right here...

 

when there are no
performance problems with your code? I guess never...

... but I still want to write "optimized" code even _before_ having any "performance problems."   Proactivity.  :)

  

> But we should not break #new: 1 and #new: 2 for HashedCollections, please.

The performance difference between #new, and #new: X where X is <= 3,
didn't bother you (or anyone else) until recently.

Because the problem is in proposal Collections-ul.871, not trunk.

 

I proposed all kinds of solutions to minimize the difference between #new
and #new:, and we seemed to agree on one of those.

Cool, let's do one of those, thanks!

 - Chris

 

[1] --         (adding 9 elements to OrderedCollection new: 10)

                100% of baseline rate, 3,860,000 per second. 259 nanoseconds per run. 2.88 % GC time.'

                (adding 9 elements to OrderedCollection new: 3)

                72% of baseline rate, 2,790,000 per second. 359 nanoseconds per run. 3.55929 % GC time.

                (Dictionary new: 1) in trunk

                21,800,000 per second. 45.9 nanoseconds per run. 13.8 % GC time.

                 (Dicitionary new: 1) with Collections-ul.871

                 '16,300,000 per second. 61.4 nanoseconds per run. 5.05899 % GC time.'

Thanks for the interesting discussion.  I'd like you to know, I'm not gung-ho about this change, but do think we should seriously consider it for the benefit of Squeak.  I think the benefit is real, but deceptive.

It seems there are two dimensions to the decision:

  - legacy / compatibility

  - API design / user-expectations

I do respect your point about legacy, that writing #new has always meant you get something that can hold up to 10 elements before needing to grow, instead of only 3.

It "sounds" reasonable, but...

Here are some certainties:

    - Allocating a 3 element array is quicker than allocating 10 element one.

Hmm not sure about that. Not for single or few objects.

Allocating many larger short lived objects will increase the rate of scavenging statistically, but this will be measurable only is allocating massively this kind of objects IMO.

    - 3 element Array's take up less memory than 10 element ones

    - consuming more RAM can lead to slowdowns due to paging or GC overhead

    - In the worst possible case (e.g., doing it over and over and nothing else), adding 9 elements to an (OrderedCollection new: 3) is 72% the speed of adding 9 elements to an (OrderedCollection new: 10). see [1]

Typical Smalltalk objects are short lived.

That's why we get a generational garbage collection.

So typical usage is unlikely to generate paging.

Case of paging can only occur if many of these objects are longer lived (and tenured), which again is not typical.

For specific usage, there might be specific optimizations like growing a bit the Eden.

Here are some uncertainties:

     - there may be some code somewhere creating many thousands of OrderedCollections (if it were only a few, it wouldn't be noticed)

     - the many thousands are all created in a very short amount of time (if it were spread out over time, it wouldn't be noticed)

     - it then stores 7-9 elements in most of the OrderedCollections

     - in spite of all of the above, the author still wrote #new instead of #new:

All your analysis is exclusively focused on a specific un-typical usage of the library...

You are then trying to bend the general purpose library tothis specific case.

IMO this should be handled with a specific optimization.

I did propose using something like a SmallDictionary that is WAY more optimized for small size than hashed collection. 

 

Collections-ul.871, just like the former version, creates dictionaries
matching those expectations, but Dictionaries returned by the new version
use less memory.
So, what's the problem?

It slowed down (Dictionary new: 1) relative to trunk, 

by a comparable margin as adding 9 elements to an (OrderedCollection new: 3) relative to an (OrderedCollection new: 10 

(see [1])

IMO this is typical biased usage of percentages... 

Saving 30% of a short duration or 30% of a long duration is not at all the same thing!

The former case is premature optimization presumably unless used in tight loops.

I still don't see a compelling reason to change #new.

In one paragraph you write about using new: "proactively" and in the next you write this is not about performance.

My opinion on the API: if I start out with no specific knowledge about the expected size of my collection or I don't think that is relevant, I use new.  That is 99% of the cases.

I expect that the standard library gives me a default that has proven to work well in most cases. By "work well" I predominantly think of time-efficiency, not space-efficiency.

We can look at other such libraries, OpenJDK also uses 10 for ArrayList: http://hg.openjdk.java.net/jdk/jdk/file/9211f6e20448/src/java.base/share/classes/java/util/ArrayList.java#l118

Also I don't expect that initial allocation with new: will always be faster. I expect that I can save reallocations later on.

That is where the time is supposed to be saved. If new is faster than new: 1, I am fine with that.