sass/libsass — pull request #563 by xzyfer (2014-10-21 14:39:24+00:00)
Title: Give maps a speed boost

> I feel the need. The need, for speed!

### Sales pitch

I started all this because our internal framework has some config bootstrapping (ab)uses maps and the performance of my original implementation was abysmal (sorry!).

### Changes

This PR gives map performance a boost. This is achieved in a couple ways, the most significant of which is backing `Sass::Map` onto an `std::unordered_map` (hash table) rather than a vector (linked list). This has a couple important benefits:

- no more `KeyValuePair` ast node (hooray for deleting code)
- hash tables enforce unique keys (#554)
- key lookups are O(1) rather the O(n)

**but unordered_maps are.. well... unordered. This is bad news for sass maps** I hear you say. Correct. To overcome this maps maintain an `` of keys ordered by insertion. The cost of maintaining this vector is relatively cheap whilst maintaining all the benefits of hash tables.

Using a hash table means that we need to define custom hashing and equality functions for `Sass::Expression`. As a bonus AST nodes lazily generate hashes and cache their hash when possible.

### Smaller improvements

- cheap lookups mean that deduping keys on `map-merge` (#554) could be done in O(1) not O(n)
- cheap lookups mean that order independent equality checks (#556) could be done in O(n) not O(n^2)
- fixed #557 by ensuring the custom hasher only deals with unquoted strings
- fixed a weird edge case with comma separated lists as keys in maps breaking when the followed a literal in parentheses

### The big reveal

I did some benchmarking of our frameworks' bootstrapping process which is entirely `@imports` and map operations.

```
Libsass 3.0

real	0m11.055s
user	0m9.823s
sys	0m1.220s

Libsass 3.0 with fast maps

real	0m3.052s
user	0m2.928s
sys	0m0.117s

Ruby sass 3.4.6

real	0m1.290s
user	0m1.220s
sys	0m0.063s
```

We still have a long way to go unfortunately but this is significant progress.