moment/moment-timezone — pull request #82 by timrwood (2014-05-18 22:16:47+00:00)
Title: Precomputed offset changes.

This is a pretty major change, so bear with me.

# Thought Process

After looking at #79, I was trying to think of how we could cache computations better.

I was thinking we could iterate through all the zones and rules and build up an array of relevant data (start or end timestamp, offset, and abbreviation). Then, when looking up the offset for a moment, we would just iterate through the array until we reached the relevant index.

I took a couple attempts at building this list from the ZoneSet, Zone, RuleSet, and Rules that are currently in place and things were becoming increasingly complicated.

Then I realized, we are already using zdump(8) to get data in this exact format for constructing the tests. Why not use zdump(8) to construct the data as well? (I know its a little redundant to use the same data source for getting data and constructing tests, but the benefits are pretty substantial).

Once I switched to using precomputed arrays of offset changes, the core lib was simplified dramatically. The RuleSets, Rules, and ZoneSets were all removed, and replaced with a new Zone object which can be constructed with a single string.

# Filesize changes

One of the concerns I had with precomputed arrays was the large number of offset changes that would need to be shipped to the client. America/St_Johns is a notable example with 239 offset changes between 1900 and 2038. I wanted to make sure we wouldn't take too much of a hit on the data filesizes.

After running some filesize tests, the increase is not that bad. moment-timezone.json contains all the old rules and zones, and moment-timezone-2.json contains the new zones. It's not a 100% direct comparison, as moment-timezone.json also contains some zone metadata and the zone aliases, but its at least a good frame of reference.

```
moment-timezone.json raw 182574 gzip 36712
moment-timezone-2.json raw 220336 gzip 25077
```

One thing to note is that the new data gzips much better than the old data.

# New Data Format

Here are the two data formats compared.

```js
// OLD
{
"zones": {
"America/Los_Angeles": [
"-7:52:58 - LMT 1883_10_18_12_7_2 -7:52:58",
"-8 US P%sT 1946 -8",
"-8 CA P%sT 1967 -8",
"-8 US P%sT"
]
},
"rules": {
"US": [
"1918 1919 2 0 8 2 0 1 D",
"1918 1919 9 0 8 2 0 0 S",
"1942 1942 1 9 7 2 0 1 W",
"1945 1945 7 14 7 23 1 1 P",
"1945 1945 8 30 7 2 0 0 S",
"1967 2006 9 0 8 2 0 0 S",
"1967 1973 3 0 8 2 0 1 D",
"1974 1974 0 6 7 2 0 1 D",
"1975 1975 1 23 7 2 0 1 D",
"1976 1986 3 0 8 2 0 1 D",
"1987 2006 3 1 0 2 0 1 D",
"2007 9999 2 8 0 2 0 1 D",
"2007 9999 10 1 0 2 0 0 S"
],
"CA": [
"1948 1948 2 14 7 2 0 1 D",
"1949 1949 0 1 7 2 0 0 S",
"1950 1966 3 0 8 2 0 1 D",
"1950 1961 8 0 8 2 0 0 S",
"1962 1966 9 0 8 2 0 0 S"
]
}
}

// NEW
"America/Los_Angeles|PST PDT PWT PPT|010102301010101010101010101010101
0101010101010101010101010101010101010101010101010101010101010101010101
0101010101010101010101010101010101010101010101010101010101010101010101
0101010101010|7uw 6ys|010101101010101010101010101010101010101010101010
1010101010101010101010101010101010101010101010101010101010101010101010
10101010101010101010101010101010101010101010101010101010101010101010|
-1Mx224 1e796 TQkw 1e796 LBHj2 7uX9S gPhS 5ePXq 1IcHC 2PtBu Rh7y 1gGm4
TOso 1e91e TOso 1e91e TOso 1e91e TOso 1e91e TOso 1gGm4 TOso 1e91e TOso
1e91e TOso 1e91e TOso 1e91e TOso 1gGm4 Rh7y 1gGm4 13XNK 13ZFS 13XNK
13ZFS 13XNK 13ZFS 16v8A 11sl2 16v8A 13ZFS 13XNK 13ZFS 13XNK 13ZFS 13XNK
13ZFS 13XNK 13ZFS 16v8A 13ZFS 13XNK 13ZFS 13XNK pois 1Izba H9Ek 1qNPi
13ZFS 16v8A 11sl2 16v8A 13ZFS 13XNK 13ZFS 13XNK 13ZFS 13XNK 13ZFS 13XNK
13ZFS 16v8A 11sl2 16v8A 13ZFS 13XNK 13ZFS 13XNK 13ZFS 13XNK WnFm 1bzOg
WnFm 1e796 TQkw 1e796 TQkw 1e796 WnFm 1bzOg WnFm 1bzOg WnFm 1e796 TQkw
1e796 TQkw 1e796 WnFm 1bzOg WnFm 1bzOg WnFm 1bzOg WnFm 1e796 TQkw 1e796
TQkw 1e796 WnFm 1bzOg WnFm 1bzOg WnFm 1e796 TQkw 1e796 TQkw 1e796 Mek0
1ogus JGZa 1ogus JGZa 1ogus Mek0 1ogus JGZa 1ogus JGZa 1ogus JGZa 1ogus
JGZa 1ogus JGZa 1ogus Mek0 1ogus JGZa 1ogus JGZa 1ogus JGZa 1ogus JGZa
1ogus Mek0 1ogus JGZa 1ogus JGZa 1ogus JGZa 1ogus JGZa 1ogus JGZa 1ogus
Mek0 1ogus JGZa 1ogus JGZa 1ogus JGZa 1ogus JGZa 1ogus Mek0 1ogus JGZa
1ogus JGZa 1ogus JGZa 1ogus JGZa 1ogus JGZa 1ogus",
```

The new version is more portable and durable. It no longer requires complicated logic to figure out which rules need to be included for which zones. Each zone is completely self sufficient.

In order to save as many bytes as possible, I used this super compact format to store the data.

The data is split into 6 sections separated by pipes.

| # | Type | Example |
|---|---------------------|-------------------------------|
| 0 | Name | `America/Los_Angeles`
| 1 | Abbreviation Map | `PST PDT PWT PPT`
| 2 | Abbreviation Index | `01010230101010101010101010101011010101010101010101010`
| 3 | Offset Map | `7uw 6ys`
| 4 | Offset Index | `01010110101010101010101010101011010101010101010101010`
| 5 | Timestamp Diff | `-1Mx224 1e796 TQkw 1e796 LBHj2 7uX9S gPhS 5ePXq 1IcHC`

**0. Name**

The canonical name of the timezone.

**1. Abbreviation Map**

A space separated list of all the abbreviations ever used in this timezone.

**2. Abbreviation Index**

A tightly packed array of indices into the abbreviation map. These are all in base62, so it will support up to 62 abbreviations per timezone. All zones have less than 10 unique abbreviations right now, so it should be fairly future proof to represent each index with a single character.

**3. Offset Map**

A space separated list of all the offsets ever used in this timezone in seconds in base62.

**4. Offset Index**

A tightly packed array of indices into the offset map. These are also in base62.

**5. Timestamp Diff**

This is where the timestamps are stored.

All these numbers represent the 'until' value of a change. The associated abbreviation and offset should only be used if the time being evaluated is *before* this value.

Because we are dealing with a sorted list of integers, we can just store the diff from the last integer rather than storing the full integer.

The first item in the array is a unix timestamp in seconds in base62. All items after the first item are numbers of seconds in base62 to be added to the previous value during unpacking.

```
packed : -100 20 30 60
unpacked : -100 -80 -50 10
```

One of the nice things about using diffs instead of whole integers is that the diffs are often the same from one year to the next, making gzipping much more effective.

I experimented with using a map + index for these values like the offsets and abbreviations, but some of the timezones with many changes overflowed the 62 value index. Additionally, the gzipped size increased when switching to a map + index, even though the un-gzipped size decreased.

# Speed

The original implementation was fairly slow. Looping through ZoneSets and Zones and RuleSets and Rules took considerable time. When memoization was added in #39, that time was significantly lessened. However, it came at the expense of memory leaks as noted in #79.

Because we no longer need to loop through ZoneSets, Zones, RuleSets and Rules, things are even faster. Here are the times for running all unit tests.

```
original 63s
memoized 18s
precomputed 7s
```

# Memory

Because we are no longer memoizing results for each new moment, the memory used is constant per timezone. Each timezone will have 3 arrays of the same length (186 in the case of America/Los_Angeles for example). One array will contain strings, and the other two will contain numbers. This will probably be even less memory that the original moment-timezone used.

Additionally, the data is only unpacked from the source string on the first time a timezone is used. Even if all the zone strings are loaded into moment-timezone, only the ones that are used will be unpacked into their array values.

# Complexity

As you can see from the moment-timezone.js diff below, the library is now significantly less complex. Of the 532 lines, 381 were deleted and 89 added for a new total of 240 lines.

The old version took 80+ dev hours to get all the tests passing, as each little edge case would break another edge case. As a result, the current code is very fragile, and refactoring is unrealistic.

With the new version, the code path for finding an offset for a moment is just a handful of statements, much more accessible for people unfamiliar with the codebase.

I think this should also make solving #27 much easier. I have taken a few stabs at solving #27, and each time hit a roadblock after a couple days of work.

# TLDR;

Switch to a new data format is faster, smaller, simpler, and doesn't leak memory.