Evaluate expressing the route stepper itself in WASM

[jj101k]

The big problem here is dynamic storage

[jj101k]

Been running tests for peak active route count in the corner-to-corner test.

At 1000: 846, 847, 846, 877, 891

At 70: 84, 61, 55, 61, 48

The theoretical worst case is w * sqrt(2) (at 1000, 1414; at 70, 99), but that's not coming up because of the highly random layout; in general they're conforming to a circle, or rather two quarter-circles. That hit at 84 is annoying because it's an outlier, rather greater than a circle would normally allow.

In principle these can be stored as just the addresses (along with, in some sense, the cost offset), meaning ~100B per side at 70 or ~3.5KB per side at 1000

[jj101k]

The tough part is moving content around. Statically you could just have content, 2 marker, content, 4 marker, content, 6 marker, content. Markers can be OOB where that's easier, since a reference to one of 1414 items (ie, < 11 bits) is cheaper than a null entry (20 bits).

Storing the positions as deltas is perfectly possible and reasonably efficient given that in most cases it's +1/+1 from the last one, but it's unclear that there would be a benefit that outweighs the complexity. For example, if it could be expressed in 4b the vast majority of the time, that'd save half the space at 70 or 80% of the space at 1000, but it'd require some UTF-8-like spanning

[jj101k]

• [ ] Find out what the actual deltas would be

[jj101k]

Hmm. This is grouped by powers of 2:

[Log] Object (index.js, line 204)
-Infinity: 27
0: 4
2: 2
3: 3
4: 5
6: 3
7: 2
8: 8
9: 2
10: 4
11: 9
12: 14
13: 26
14: 19
15: 12
16: 2
Object Prototype

[jj101k]

Should have clarified, that's at 300x300. So fully described co-ordinates need 16.5 bits; here the test is |(a.x-b.x)*(a.y-b.y)|, taking the smallest number of bits that could fit it, so "16" covers everything from about |181| * |181| (32768) to |256| * |256| (65535) - meaning that the furthest points must be adjacent in the list (clearly I haven't thought much about the list order). There are also, as is clear here, 27 route points which have the same coordinates.

[jj101k]

As-is, if that data were stored as its raw bits (ignoring the off-by-1 to the extent that such is possible), it'd need 1401 of them; at full size, 2326. So, nothing to be saved there - but what is up about the order?

[jj101k]

It's strange, on any given pass new entries would all be emitted in the same order as the originating old ones, which means that order would, broadly, be retained.

[jj101k]

Oh, that's stupid, x * 0 is 0 of course.

[jj101k]

I suppose that any given offset would be a series of +4 moves followed by a series of +6 moves which would at least produce 50/50 dissimilarity

[jj101k]

At 70x70

Unmodified route distances:

Object = $2
5: 1
16: 1
17: 1
21: 1
22: 1
30: 1
42: 1
44: 1
54: 1
84: 1
88: 1
104: 1
128: 2
180: 1
195: 1
260: 1
320: 1
330: 1
520: 1
550: 1
594: 1
693: 1
798: 1
832: 1
1804: 1
1892: 1
Object Prototype

Simple sort (x then y):

Object = $4
4: 1
5: 1
10: 3
12: 3
15: 1
16: 1
20: 1
21: 1
32: 1
42: 1
44: 1
45: 1
48: 1
54: 1
66: 2
75: 1
80: 2
84: 1
96: 1
108: 1
128: 1
Object Prototype

Basic attempt at radial sort (x/y):

Object = $5
4: 1
5: 1
10: 3
12: 3
15: 1
20: 1
21: 2
27: 1
32: 1
42: 1
45: 3
48: 1
56: 1
66: 2
80: 1
110: 1
128: 3
Object Prototype

[jj101k]

27 in total, so medians at: 180; 42; 32. Bit counts for reasonable sizes:

Unmodified:

4 (<16): 1 8 (<256): 15 12 (<2048): 11

Simple:

4 (<16): 9 8 (<256): 18 12 (<2048): 0

Radial:

4 (<16): 9 8 (<256): 18 12 (<2048): 0

[jj101k]

So here, 32 bytes vs 22.5 bytes (vs 22.5 byes), as compared to the full ~42 bytes

[jj101k]

Raw distances:

24 bytes 16.5 bytes 16.4 bytes

[jj101k]

Overbudgeted for 100B per side here, so practically this isn't a big problem - although notably the budget is for 1s (short side) max where the actual max is 2s-1 where one rank is a candidate for diagonal expansion and the next any-direction.

[jj101k]

Since they're all walkable, delta forms would be reasonable - the only real question is whether there is a cheap way to get a more viable order.

[jj101k]

Testing a simple correction to the diagonal list at 70:

Unmodified:

Object = $1
3: 4
4: 3
5: 2
28: 1
42: 1
66: 1
116: 1
135: 1
140: 1
155: 1
300: 1
320: 1
432: 1
448: 1
513: 1
560: 1
759: 1
792: 1
812: 1
836: 1
936: 1
962: 1
1110: 1
1116: 1
1794: 1
Object Prototype

No appreciable improvement in the extremes, although more of the values are in the small numbers. Of the 31 present, 9 fit in 2^4, 16 in 2^8 and all in 2^12.

Simple sort ((a, b) => (a.x - b.x) || (a.y - b.y)):

Object = $3
3: 4
4: 2
5: 4
6: 1
7: 1
8: 3
9: 1
10: 1
12: 1
14: 1
26: 1
28: 1
31: 1
40: 1
52: 1
58: 1
63: 1
100: 1
104: 1
143: 1
473: 1
528: 1
Object Prototype

That's 19 fit in 2^4, 29 in 2^8 and all in 2^12 (strictly 2^10). Still so much better.

Sort by angle ((a, b) => (a.x/a.y - b.x/b.y)):

Object = $4
3: 3
4: 4
5: 2
6: 1
7: 1
8: 3
9: 1
10: 1
12: 1
14: 1
20: 1
21: 1
28: 1
30: 1
40: 1
52: 2
100: 1
108: 1
143: 1
168: 1
176: 1
180: 1
Object Prototype

That's 18 in 2^4, all in 2^8

[jj101k]

Compare previous unsorted, which was 1 in 2^4, 15 in 2^8, 26 in 2^12, ie in half-bytes it's 31 bytes total (compared to the 52 bytes that completely traditional storage would do, or 40 bytes if optimally stored as coordinates)

[jj101k]

Corrected diagonal order (on a different test of course): 9 0.5 + 7 + 15 1.5 = 34B +simple sort: 19 0.5 + 10 + 2 1.5 = 22.5B +angular sort: 18 * 0.5 + 13 + 0 = 22B

So, no appreciable difference at all.

[jj101k]

Seems like I can sort when concatenating without an appreciable increase in cost

[jj101k]

A couple of problems though:

1. Delta encoding is awkward to sort, even though you can be sure that within a block it will only get shorter
2. The whole set naturally needs to move to ensure that it fits

Also don't really want full-scale scratch space for inbound items, because that is a pretty significant scale

[jj101k]

And if sorting something other than delta, might as well just store them all at some sensible approximation of max.

Certainly a sensible initial position

[jj101k]

Noting that merge sort with delta retention wouldn't be all that difficult