Shopify/batman — pull request #348 by hornairs (2012-03-01 17:34:21+00:00)
Title: Array backed Set

I submit this for your perusal @jamesmacaulay, @nciagra and @tobi, I am not confident it should be merged.

`SimpleSet` could be implemented on top of an array instead of a `Hash`. With the hash, items end up as keys in the hash, so that we can check for membership in the set and guarantee that an item appears in a set only once. With the array, we avoid having the whole `SimpleHash` object which backs the set and instead just use a "ligherweight" array at the expense of having to do O(n) searches through it when checking membership which happens on both `add` and `remove`.

Now, the performance characteristics of the two. The whole thing is complicated by the fact that since `SimpleHash`'s implementation is a-changin', Set's performance characteristics change with that too.

### Memory Usage

```coffeescript
set = new Batman.SimpleSet

Watson.trackMemory 'simple set memory usage with strings', 10000, (i) ->
set.add "fooooooo" + i
if i % 2000 == 0
set.clear()
```

```coffeescript
set = new Batman.SimpleSet

Watson.trackMemory 'simple set memory usage with objects', 10000, (i) ->
set.add new Clunk
if i % 2000 == 0
set.clear()
```

gives

[![][1]][1]

The blue line is the interesting one. It gives vastly reduced memory usage for both string and object keys, whereas the hash optimizations in the other branch give equivalent memory reduction, but only for string Set members, which probably doesn't happen all that often.

### Membership and Addition Speed

[![][2]][2]

From left to right in the above image we have the array backed set, master, and Set on top of the hash_optimizations. The height of the bar represents the mean total time spent checking membership of and adding 100 objects, so lower is better. The membership check happens linearly in that it checks the first item in the storage array first, the second item second, and so on and so forth. I believe this means the mean is properly indicative of the mean membership check time.

Based on my best estimation the performance of these two operations hasn't changed much. The benchmarks aren't rock solid in terms of error margins, so I would estimate that the changing Set to being backed by an array makes things marginally slower, but not by much at all. This is somewhat counter to what I would have guessed: that switching to an O(n) search through the underlying storage array is slower. Perhaps the overhead associated with calling into the hash and letting it do its thing with potentially colliding keys is just as slow in practice.

### Removal Speed

Code for the "standard" removal:

```coffeescript
getSet = ->
set = new Batman.Set
set.add(clunk) for clunk in clunks
set

set = getSet()

suite.add 'object member removal', () ->
for clunk in clunks
set.remove(clunk)
true
, {
onCycle: -> set = getSet()
}
```
Build a set full of 100 clunky objects, and then remove them one by one in the order they were added.

Code for the "haystack removal":

```coffeescript
moreClunks = for i in [0..100]
number = generator.next()
new Clunk({number})

sortedMoreClunks = moreClunks.sort (a, b) -> a.number - b.number

getSet = ->
set = new Batman.Set
set.add(clunk) for clunk in clunks
set.add(clunk) for clunk in moreClunks
set

set = getSet()

suite.add 'haystack object member removal', () ->
# Remove clunks in a deterministic but random order
for clunk in sortedMoreClunks
set.remove(clunk)
true
, {
onCycle: -> set = getSet()
}
```

Build a set full of 200 clunky objects, and remove the last 100 in a random order. The first 100 objects just hang out.

#### Graph

[![][3]][3]

Interestingly things have changed.

Vanilla removal has actually gotten faster by changing to array backing. I believe this a bit of a red herring because of the way the benchmark works: items are removed in the order they were added, so the items at the start of the underlying storage array are removed first. This means the indexOf search for the item finds it very soon after it starts every iteration through this benchmark. Truth be told however, this is a common situation in Batman because the vast majority of sets are very small. Many many Sets hold only a few Property or Event objects and thus the removal algorithms will find the objects they are looking in < 10 steps through the array, so I say this is a net win.

However, haystack removal is a different story. "Haystack" means that the items are removed in a random order. In an attemp to highlight the deficiencies of the array backed set, we run it on Sets who have 100 items which areadded first and then left alone, so that all indexOf checks have to traverse that before finding anything useful.

The array backed set is slower for "haystack" removal with objects but the performance remains the same for the hash backed sets, verifying that membership checks are closer to O(1) when using the hash backing, and closer to O(n) when using the array backing. Presumably this is because the `indexOf` on the storage array is O(n), and maybe the actual `splice` used for removal too. This is the drawback of using array backed sets. However, haystack removal with strings gets way faster, which I can't quite explain. My best guess would be arrays full of strings have underlying optimizations in the VM, so this result may be unreliable across various other implementations.

So, do we switch it? We can't merge this yet because some subtle semantics of Set changed which these changes and desipte the Set test suite passing some other seemingly unrelated tests fail, but I only want to hunt down those bugs if the performance increase is worth it.

[1]: https://img.skitch.com/20120301-8qq75r56m5rtcewbdai78y6f2y.jpg
[2]: https://img.skitch.com/20120301-rgiruwbtmui43hc8uske3hcwc3.jpg
[3]: https://img.skitch.com/20120301-djf92n8tp9n4tbinxne9phhasm.jpg