9/30/2011

09-30-11 - String Match Results Part 5 + Conclusion

Finally for completeness, some of the matchers from Tornado in FreeArc. These are basically all standard "cache table" style matchers, originally due to LZRW, made popular by LZP and LZO. The various Tornado settings select different amounts of hash rows and ways.

As they should, they have very constant time operation that goes up pretty steadily from Tornado -3 to -7, because there's a constant number of hash probes per match attempt.


totals : match len : clocks
Test_MMC1 : 0.663028 , 231.254818 
Test_Hash1 : 0.662718 , 64.888003 
Test_Tornado_3 : 0.630377 , 19.658834 
Test_Tornado_4 : 0.593174 , 28.456055 
Test_Tornado_5 : 0.586540 , 40.546146 
Test_Tornado_6 : 0.580042 , 56.841156 
Test_Tornado_7 : 0.596584 , 141.432393 

There may be something wrong with my Tornado wrapper as the -3 matcher actually finds the longest total length. I dunno. The speeds look reasonable. I don't really care much about these approximate matchers because the loss is hard to quantify, so there you go (normally when I see an anomaly like that I would investigate it to make sure I understand why it's happening).

0 = ares_merged.gr2_sec_5.dat
1 = bigship1.x
2 = BOOK1
3 = combined.gr2_sec_3.dat
4 = GrannyRocks_wot.gr2
5 = Gryphon_stripped.gr2
6 = hetero50k
7 = lzt20
8 = lzt21
9 = lzt22
10 = lzt23
11 = lzt24
12 = lzt25
13 = lzt27
14 = lzt28
15 = lzt29
16 = movie_headers.bin
17 = orange_purple.BMP
18 = predsave.bin


Conclusion : I've got to get off string matching so this is probably the end of posts on this topic.

MMC looks promising but has some flaws. There are some cases that trigger a slowness spike in it. Also it has some bad O(N^2) with unbounded match length ("MMC2") so I have to run it with a limit ("MMC1") which removes some of its advantage over LzFind and Hash1 and other approximate matchers. (without the limit it has the advantage of being exact). It's also a GPL at the moment which is a killer.

LzFind doesn't have anything going for it really.

For approximate/small-window matching I don't see any reason to not use the classic Zip hash chain method. I tried a few variants of this, like doing a hash chain to match the first 4 bytes and then link listing off that, and all the variants were worse than the classic way.

For large window / exact matching / optimal parsing, a correct O(N) matcher is the way to go. The suffix-array based matcher is by far the easiest for your kids to implement at home.

09-30-11 - String Match Results Part 4

Okay, finally on to greedy parsing. Note with greedy parsing the average match length per byte is always <= 1.0 (it's actually the % of bytes matched in this case).

Two charts for each , the first is clocks per byte, the second is average match length. Note that Suffix5 is just for reference and is neither windowed nor greedy.

got arg : window_bits = 16

got arg : window_bits = 17

got arg : window_bits = 18

Commentary :

Okay, finally MMC beats Suffix Trie and LzFind, this is what it's good at. Both MMC and LzFind get slower as the window gets larger. Surprisingly, the good old Zip-style Hash1 is significantly faster and finds almost all the matches on these files. (note that LzFind1 and Hash1 both have search limits but MMC does not)


test set :

0 = ares_merged.gr2_sec_5.dat
1 = bigship1.x
2 = BOOK1
3 = combined.gr2_sec_3.dat
4 = GrannyRocks_wot.gr2
5 = Gryphon_stripped.gr2
6 = hetero50k
7 = lzt20
8 = lzt21
9 = lzt22
10 = lzt23
11 = lzt24
12 = lzt25
13 = lzt27
14 = lzt28
15 = lzt29
16 = movie_headers.bin
17 = orange_purple.BMP
18 = predsave.bin


The same matchers ; greedy, 16 bit window, on the stress tests :

LzFind does not do well at all on the stress tests. (note that LzFind1 and MMC1 are length-limitted; LzFind1 and Hash1 are "amortized" (step limitted)).

0 = stress_all_as 
1 = stress_many_matches 
2 = stress_search_limit 
3 = stress_sliding_follow 
4 = stress_suffix_forward 
5 = twobooks

09-30-11 - String Match Results Part 3

Still doing "optimal" (non-greedy parsing) but now lets move on to windowed & non-exact matching.

Windowed, possibly approximate matching.

Note : I will include the Suffix matchers for reference, but they are not windowed.

16 bit window :

Clocks per byte :

Average Match len :

This is what LzFind is designed for and it's okay at it. It does crap out pretty badly on the rather degenerate "particles.max" file, and it also fails to find a lot of matches. (LZFind1 has a maximum match length of 256 and a maximum of 32 search steps, which are the defaults in the LZMA code; LzFind2 which we saw before has those limits removed (and would DNF on many of these files)).

lztest is :

0 = almost_incompressable
1 = bigship1.x
2 = Dolphin1.x
3 = GrannyRocks_wot.gr2
4 = Gryphon_stripped.gr2
5 = hetero50k
6 = movie_headers.bin
7 = orange_purple.BMP
8 = particles.max
9 = pixo_run_animonly_stripped.gr2
10 = poker.bin
11 = predsave.bin
12 = quick.exe
13 = RemoteControl_stripped.gr2
14 = ScriptVolumeMgr.cpp

09-30-11 - String Match Results Part 2b

Still on optimal parsing, exact matching, large window :

Chart of clocks per byte, on each file of a test set :

On my "lztest" data set :


0 = almost_incompressable
1 = bigship1.x
2 = Dolphin1.x
3 = GrannyRocks_wot.gr2
4 = Gryphon_stripped.gr2
5 = hetero50k
6 = movie_headers.bin
7 = orange_purple.BMP
8 = particles.max
9 = pixo_run_animonly_stripped.gr2
10 = poker.bin
11 = predsave.bin
12 = quick.exe
13 = RemoteControl_stripped.gr2
14 = ScriptVolumeMgr.cpp

"lztest" is not a stress test set, it's stuff I've gathered that I think is roughly reflective of what games actually compress. It's interesting that this data set causes lots of DNF's (did not finish) for MMC and LzFind.

Suffix5 (the real suffix trie) is generally slightly faster than the suffix array. It should be, of course, if I didn't do a bonehead trie implementation, since the suffix array method basically builds a trie in the sort, then reads it out to sorted indexes, and then I convert the sorted indexes back to match lengths.

Good old CCC (Calgary Compression Corpus) :


0 = BIB
1 = BOOK1
2 = BOOK2
3 = GEO
4 = NEWS
5 = OBJ1
6 = OBJ2
7 = PAPER1
8 = PAPER2
9 = PAPER3
10 = PAPER4
11 = PAPER5
12 = PAPER6
13 = PIC
14 = PROGC
15 = PROGL
16 = PROGP
17 = TRANS

I won't be showing results on CCC for the most part because it's not very reflective of real world modern data, but I wanted to run on a set where MMC and LzFind don't DNF too much to compare their speed when they do succeed. Suffix Trie is almost always very close to the fastest except on paper4 & paper5 which are very small files.


0 = BIB
1 = BOOK1
2 = BOOK2
3 = GEO
4 = NEWS
5 = OBJ1
6 = OBJ2
7 = PAPER1
8 = PAPER2
9 = PROGC
10 = PROGL
11 = PROGP
12 = TRANS

Two new tests in the mix.

Test_Hash1 : traditional "Zip" style fixed size hash -> linked list. In this run there's no chain limit so matching is exact.

Test_Hash3 : uses cblib::hash_table (a reprobing ("open addressing" or "closed hashing", I prefer reprobing)) to hash the first 4 bytes then a linked list. I was surprised to find that this is almost the same speed as Hash1 and sometimes faster, even though it's a totally generic template hash table (that is not particularly well suited to this usage).

09-30-11 - BMWs

I think the E46 M3 is almost the most perfect car ever made. Great engine, plenty of room, great handling (after you dial out the factory understeer); comfortable enough to drive anywhere, but tight enough to toss. I wish it wasn't quite so ugly, and I wish it weighed about 300 pounds less, and I wish it didn't have a leather interior which is invariably gross by now (seriously? can we fucking get technical fabric in cars already? it's breathable, near waterpoof, doesn't get hot or cold, doesn't get ruined by water or sun, it's been the obvious correct material for car interiors for like 10 years now, stop being such ass hats).

E46 M3 prices from cars.com :

Progression of M3 power-to-weights over the years : (with the 1M thrown in since it's the real small M sedan of the present)


E30 2865 / 250 (*) = 11.5 (pounds per hp)
E36 3220 / 316 = 10.2
E46 3415 / 338  3443? = 10.1
1M  3461 / 335  3329? 3296? =  = 10.1 (**)
E92 3704-3900 / 414 = 9.2

correct/comparable weights are hard to find. Both the manufacturer weights and magazine weights are not reliable. You need the regulatory DIN weight or something but I can't find a good source for that (Wikipedia is no good). Anyway, the details may be a bit off, but the power-to-weights of M cars have changed surpisingly little over the years. The powers have gone up, but so have the weights, only slightly slower.

(* = the E30 S14 engine made more like 200 hp stock, but can be reasonably easy brought up to "race spec" 250 hp using modern electronic fuel injection and a few other cheap mods; unlike the other engines, the S14 was actually raced and is reliable even at higher output).
(** = the 1M can easily make 380 hp or so with standard turbo mods).

Before about 2001 the US versions of most BMW's were crippled. Either worse versions of the engines or completely different engines.

The Z3 "M coupe" shooting-brake is supposedly one of the best handling cars ever made (up there with the NSX and I'm not sure what else). The good one is the late model 2001-2002 which got the E46 M3 engine. Unfortunately the public has figured this out and they're now a bit of a collectors item for enthusiasts; prices have stabilized in the $30k-40k range, around double prices of the earlier small engine Z3 M Coupe. I'm a big fan of how ugly it is, and I love that it has the practicality of a wagon, but I hear the cockpit is a bit small.

The later M coupe is extremely comparable to a Cayman :


E86 Z4 M Coupe (2006-2008) : 330 hp, 3200 pounds = 9.7 (pounds per hp)
997.2 Cayman   (2009-2011) : 320 hp, 3000 pounds = 9.4

The M Coupe makes better noises and the engine is easier to tune up, it's also more analog, more raw. The Cayman actually has a lot more cabin room and luggage room ; the M is rather uncomfortably cramped, and I didn't love the feel of sitting over the rear axle in a car with a huge hood. The M will certainly depreciate less, and is marginally less douchey.

There's a large spec E30 (E30 325i) amateur race class. It's a very cheap race class to get into with a very strict spec, it looks like a lot of fun. Maybe I'll do something like that in my retirement. Cars like that are called "momentum cars" by racers because they have very little acceleration; not much fun on the street, but they can still be great on a track because it takes a lot of skill to get the right line to keep speed through corners in traffic.

09-30-11 - String Match Results Part 2

The first and simplest set of results are the ones where non-O(N) algorithms make themselves known.

Optimal parsing, large window.

The candidates are :

SuffixArray1 : naive matcher built on divsufsort
SuffixArray2 : using the forward-offset elimination from this post
Suffix2 : Suffix Trie with follows and path compression but missing the bits in this post
Suffix3 : Suffix Trie without follow
Suffix5 : fully working Suffix Trie
MMC1 : MMC with max match length of 256
MMC2 : MMC with no limit
LzFind1 : LzFind (LZMA HC4 - binary tree) with max ML of 256 and step limit of 32
LzFind2 : LzFind with no max ML or step limit

Note : LzFind was modified from LZMA to not record all matches, just the longest, to make it more like the competitors. MMC was modified to make window size a variable.

In all cases I show :


Test_Matcher : average match length per byte , average clocks per byte

And with no further ado :

got arg : window_bits = 24
working on : m:\test_data\lz_stress_tests

loading file : m:\test_data\lz_stress_tests\stress_many_matches
Test_SuffixArray1 : 32.757760 , 164.087948 
Test_SuffixArray2 : 32.756953 , 199.878476 
Test_Suffix2 : 32.757760 , 115.846130 
Test_Suffix3 : 31.628279 , 499.722569 
Test_Suffix5 : 32.757760 , 184.172167 
Test_MMC2 : 32.757760 , 1507.818166 
Test_LzFind2 : 32.757760 , 576.154370 

loading file : m:\test_data\lz_stress_tests\stress_search_limit
Test_SuffixArray1 : 823.341331 , 182.789064 
Test_SuffixArray2 : 823.341331 , 243.492241 
Test_Suffix2 : 823.341331 , 393.930504 
Test_Suffix3 : 807.648294 , 2082.447274 
Test_Suffix5 : 823.341331 , 91.699276 
Test_MMC2 : 823.341331 , 6346.400206 
Test_LzFind2 : 823.341331 , 1807.516994 

loading file : m:\test_data\lz_stress_tests\stress_sliding_follow
Test_SuffixArray1 : 199.576550 , 189.029462 
Test_SuffixArray2 : 199.573198 , 220.316868 
Test_Suffix2 : 199.576550 , 95.225780 
Test_Suffix3 : 198.967622 , 2110.521111 
Test_Suffix5 : 199.576550 , 106.019526 
Test_MMC2 : 199.576550 , 36571.382020 
Test_LzFind2 : 199.576550 , 1249.184412 

loading file : m:\test_data\lz_stress_tests\stress_suffix_forward
Test_SuffixArray1 : 5199.164464 , 6138.802402 
Test_SuffixArray2 : 5199.164401 , 213.675569 
Test_Suffix2 : 5199.164464 , 12901.429712 
Test_Suffix3 : 5199.075953 , 32152.812339 
Test_Suffix5 : 5199.164464 , 145.684678 
Test_MMC2 : 5199.016562 , 6652.666440 
Test_LzFind2 : 5199.164464 , 11739.369336 

loading file : m:\test_data\lz_stress_tests\stress_all_as
Test_SuffixArray1 : 21119.499148 , 40938.612689 
Test_SuffixArray2 : 21119.499148 , 127.520147 
Test_Suffix2 : 21119.499148 , 88178.094886 
Test_Suffix3 : 21119.499148 , 104833.677202 
Test_Suffix5 : 21119.499148 , 119.676823 
Test_MMC2 : 21119.499148 , 25951.480871 
Test_LzFind2 : 21119.499148 , 38581.431558 

loading file : m:\test_data\lz_stress_tests\twobooks
Test_SuffixArray1 : 192196.571348 , 412.356092 
Test_SuffixArray2 : 192196.571348 , 420.437773 
Test_Suffix2 : 192196.571348 , 268.524287 
Test_Suffix3 : DNF
Test_Suffix5 : 192196.571348 , 292.777726 
Test_MMC2 : DNF 
Test_LzFind2 : DNF 

(DNF = Did Not Finish = over 100k clocks per byte).

Conclusion : SuffixArray2 and Suffix5 both actually work and are correct with no blowup cases.

SuffixArray1 looks good on the majority of files (and is slightly faster than SuffixArray2 on those files), but "stress_suffix_forward" clearly calls it out and shows the break down case.

Suffix2 almost works except on the degenerate tests due to failure to get some details of follows quite right ( see here ).

Suffix3 just shows that a Suffix Trie without follows is some foolishness.

We won't show SuffixArray1 or Suffix2 or Suffix3 again.

MMC2 and LZFind2 both have bad failure cases. Both are simply not usable if you want to find the longest match at every byte. We will revisit them later in other usages though and see that they are good for what they're designed for.

I've not included any of the hash chain type matchers in this test because they all obviously crap their pants in this scenario.

09-30-11 - String Match Results Part 1

I was hoping to make some charts and graphs, but it's just not that interesting. Anyhoo, let's get into it.

What am I testing? String matching for an LZ-type compressor. Matches must start before current pos but can run past current pos. I'm string matching only, not compressing. I'm counting the total time and total length of matches found.

I'm testing match length >= 4. Matches of length 2 & 3 can be found trivially by table lookup (though on small files this is not a good way to do it). Most of the matchers can handle arbitrary min lengths, but this is just easier/fairer for comparison.

I'm testing both "greedy" (when you find a match step ahead its length) and "optimal" (find matches at every position). Some matchers like the suffix tree ones don't really support greedy parsing, since they have to do all the work at every position even if you don't want the match there.

I'm testing windowed and non-windowed matchers.

I'm testing approximate and non-approximate (exact) matchers. Exact matchers find all matches possible, approximate matchers find some amount less. I'm not sure the best way to show the approximation vs. speed trade off. I guess you want a "pareto frontier" type of graph, but what should the axes be?

Also, while I'm at it, god damn it!

MAKE YOUR CODE FREE PEOPLE !!

(and GPL is not free). And some complicated personal license is a pain in the ass. I used to do this myself, I know it's tempting. Don't fucking do it. If you post code just make it 100% free for all uses. BSD license is an okay choice.

Matchers I'm having trouble with :


Tornado matchers from FreeArc - seem to be GPL (?)

MMC - GPL

LzFind from 7zip appears to be public domain. divsufsort is free. Larsson's slide is free.

09-30-11 - Don't use memset to zero

A very common missed optimization is letting the OS zero large chunks of memory for you.

Everybody just writes code like this :


U32 * bigTable = malloc(20<<20);
memset(bigTable,0,20<<20);

but that's a huge waste. (eg. for large hash table on small files the memset can dominate your time).

Behind your back, the operating system is actually running a thread all the time as part of the System Idle Process which grabs free pages and writes them with zero bytes and puts them on the zero'ed page list.

When you call VirtualAlloc, it just grabs a page from the zeroed page list and hands it to you. (if there are none available it zeroes it immediately).

!!! Memory you get back from VirtualAlloc is always already zeroed ; you don't need to memset it !!!

The OS does this for security, so you can never see some other app's bytes, but you can also use it to get zero'ed tables quickly.

(I'm not sure if any stdlib has a fast path to this for "calloc" ; if so that might be a reason to prefer that to malloc/memset; in any case it's safer just to talk to the OS directly).

ADDENDUM : BTW to be fair none of my string matchers do this, because other people's don't and I don't want to win from cheap technicalities like that. But all string match hash tables should use this.

9/29/2011

09-29-11 - Suffix Tries 3 - On Follows with Path Compression

Some subtle things that it took me a few days to track down. Writing for my reference.

1. Follows updates should be a bit "lazy". With path compression you aren't making all the nodes on a suffix. So when you match at length 5, the follow at length 4 might not exist. (I made a small note on the consequences of this previously . Even if the correct follow node doesn't exist, you should still link in to the next longest follow node possible (eg. length 3 if a 4 doesn't exist). Later on the correct follow might get made, and then if possible you want to update it. So you should consider the follows links to be constantly under lazy update; just because a follow link exists it might not be the right one, so you may want to update it.

eg. say you match 4 bytes of suffix [abcd](ef..) at the current spot. You want to follow to [bcd] but there is no length 3 node of that suffix currently. Instead you follow to [bc] (the next best follow available) , one of whose children is [dxy], you now split the [dxy] to [d][xy] and add [ef] under [d]. You can then update the follow from the previous node ([abcd]) to point at the new [bc][d] node.

2. It appears that you only need to update one follow per byte to get O(N). I don't see that this is obvious from a theoretical standpoint, but all my tests pass. Say you trace down a long suffix. You may encounter several nodes that don't have fully up to date follow pointers. You do not have to track them all and update them all at the next byte. It seems you can just update the deepest one (not the deepest node, but the deepest node that needs an update). (*)

3. Even if your follow is not up to date, you can still use the gauranteed (lastml-1) match len to good advantage. This was a big one that I missed. Say you match 4096 bytes and you take the follow pointer, and it takes you to a node of depth 10. You've lost a lot of depth - you know you must match at least 4095 bytes and you only have 10 of them. But you still have an advantage. You can descend the tree and skip all string compares up to 4095 bytes. In particular, when you get to a leaf you can immediately jump to matching 4095 of the leaf pointer.

4. Handling of EOF in suffix algorithms is annoying; it needs to act like a value outside the [0,255] range. The most annoying case is when you have a degenerate suffix like aaaa...aaaEOF , because the "follow" for that suffix might be itself (eg. what follows aaa... is aa..) depending on how you handle EOF. This can only happen with the degenerate RLE case so just special casing the RLE-to-EOF case avoids some pain.

ADDED : There's a trivial solution to handling EOF easily : 09-10-14 - Suffix Trie EOF handling

(* = #2 is the thing I have the least confidence in; I wonder if there could be a case where the single node update doesn't work, or if maybe you could get non-O(N) behavior unless you have a more clever/careful update node selection algorithm)

9/28/2011

09-28-11 - String Matching with Suffix Arrays

A suffix sorter (such as the excellent divsufsort by Yuta Mori) provides a list of the suffix positions in an array in sorted order. Eg. sortedSuffixes[i] is the ith suffix in order.

You can easily invert this table to make sortLookup such that sortLookup[ sortedSuffix[i] ] == i . eg. sortLookup[i] is the sort order for position i.

Now at this point, for each suffix sort position i, you know that the longest match with another suffix is either at i-1 or i+1.

Next we need the neighboring pair match lengths for the suffix sort. This can be done in O(N) as previously described here . So we now have a sortSameLen[] array such that sortSameLen[i] tells you the match length between (sorted order) elements i and i+1.

Using just these you can find all the match lengths for any suffix in the array thusly :


For a suffix start at index pos
Find its sort order : sortIndex = sortLookup[pos]
In each direction (+1 and -1)
current_match_len = infinite
step to next sort index
current_match_len = MIN(current_match_len,sortSameLen[sort index])

Okay. This is all old news. But it has a problem that has been discussed previously .

When matching strings for LZ and such, we don't want the longest match in the array, we want the longest match that occurs earlier. Handled naively this ruins the great O() performance of suffix array string matching. But you can do better.

Run Algorithm Next Index with Lower Value on the sortedSuffix[] array. This provides an array nextSuffixPreceding[]. This is exactly what you need - it provides the next closest suffix with a preceding index.

Now instead of the longest match being at +1 and -1, the longest match is at nextSuffixPreceding[i] and priorSuffixPreceding[i].

There's one last problem - if my current suffix is at position pos, and I look up si = sortIndex[pos] and from that nextSuffixPreceding[si] - I need to walk up to that position one by one doing MIN() on the adjacent pair match lengths (sortSameLen). That ruins my O() win.

But there's a solution - simply build the match length as well when you run "next index with lower value". This can be done easily by tracking the match length back to the preceding "fence". This adds no complexity to the algorithm.

The total sequence of operations is :


sort suffixes : O(NlogN) or so

build sort lookup : O(N)

build sort pair same len : O(N)

build next/prior pos preceding with match lengths : O(N)

now to find a match length :

at position "pos"
si = sortLookup[pos]
for each direction (following and preceding)
  matchpos = nextSuffixPreceding[si]
  matchlen = nextSuffixPreceding_Len[si]

that is, the match length lookup is a very simple O(1) per position (or O(N) for all positions).

One minor annoyance remains, which is that the suffix array string searcher does not provide the lowest offset for a given length of match. It gives you the closest in suffix order, which is not what you want.

09-28-11 - Rugby

God damn rugby is a fucking joyous sport to watch.

1. No commercials. I just can't watch sports with commercials any more. Right when you start to get into the action you have to see some shit about Geico or Aflac or some shit. OMG what could be more of a scam than supplemental insurance. Maybe I should insure my insurance rate. And insure against my insurance company going bankrupt. And some supplemental umbrella insurance. Now I'm upset, no more watching commercials.

2. No breaks between plays. No instant replay. No timeouts. Just action action all the time.

3. Advantage. I think I did a post about this long ago, but the "advantage" rule for penalties is just so much fucking win. It means that you don't have to stop play for every piddly penalty, you let play keep going as long as the penalizing team has not gained an advantage from the penalty (more precisely, play continues as long as the team that was infringed upon is at an advantage compared to the position they were in at the time of the penalty). This sounds complex but is not and is just 100% win.

4. The refs. The refs in rugby are just uniformly superb. I'm not quite sure why they're so much better than any other sport. They have more autonomy and more freedom to make judgement calls, and they seem to do so well. One aspect perhaps is that most rugby refs have played a bit at the professional level, which I think is rare in other sports.

5. The game is (usually) not decided by penalties. I just can't watch basketball or soccer because of this. Penalties should encourage players to stick to the spirit of the game, the game shouldn't become all about the points you can get off penalties. It ruins the game.

6. The players aren't divers or whiners (mostly). In other sports you see the players taking dives, trying to draw fouls, or going and begging to the ref after plays. WTF, do you have no self respect? You're a grown man and you're diving and whining? WTF. I wonder if they secretly practice flopping in basketball and soccer training camps, or is that something (like taking steroids) that you're supposed to figure out on your own in a kind of nudge-nudge-wink-wink way. Maybe a veteran player takes the rookie under his wings and does some supplement flop and beg practice. I don't know how you can be a fan of a player like Robert Horry or Zidane; oh yeah, I really admire the way they fake being fouled, it's so graceful.

Anyway, I feel like most ruggers just want to get back to play. They want to win the game by smashing through their opponents with ball in hand, not by begging to the ref. And that I respect.

(I must say, watching the recent NZ-France World Cup match I was absolutely disgusted by the sleazy play of the French. Several soccer-style dives trying to draw penalty, one attempt at drawing "obstruction", and the very sleazy try by kicking off while the ref was talking, just absolutely scummy soccer-style tactics, I hope they get their eyes poked in every ruck).

7. Toughness. It's great to watch some big men just brutalize each other. This used to be part of the appeal of American Football but they've all become such delicate flowers now ; oo I have a stubbed toe better get off the field. Back in the day you had guys like Ronnie Lott who gave up a chunk of their thumb to stay on the field. That sort of macho insanity still exists in rugby ; if you get a sprain or even a broken bone or something of course you fucking stay on the field, what are you a pussy? You get off the field when your team doesn't need you any more.

Most of the WC games I've seen so far have been very pretty, good games of rugby, with good discipline and a few flashes of beautiful ball movement and big runs. That's not always the case, though, it can degenerate into a very ugly game. With unskilled teams you get scrums that don't hold together and constantly have to restart, you get lots of bobbled and dropped balls, they can't put together phases, and those games are no fun to watch.

09-28-11 - Algorithm - Next Index with Lower Value

You are given an array of integers A[]

For each i, find the next entry j (j > i) such that the value is lower (A[j] < A[i]).

Fill out B[i] = j for all i.

For array size N this can be done in O(N).

Here's how :

I'll call this algorithm "stack of fences". Walk the array A[] from start to finish in one pass.

At i, if the next entry (A[i+1]) is lower than the current (A[i]) then you have the ordering you want immediately and you just assign B[i] = i+1.

If not, then you have a "fence", a value A[i] which is seeking a lower value. You don't go looking for it immediately, instead you just set the current fence_value to A[i] and move on via i++.

At each position you visit when you have a fence, you check if the current A[i] < fence_value ? If so, you set B[fence_pos] = i ; you have found the successor to that fence.

If you have a fence and find another value which needs to be a fence (because it's lower than its successor) you push the previous fence on a stack, and set the current one as the active fence. Then when you find a value that satisfies the new fence, you pop off the fence stack and also check that fence to see if it was satisfied as well. This stack can be stored in place in the B[] array, because the B[] is not yet filled out for positions that are fences.

The pseudocode is :


fence_val = fence_pos = none

for(int i=1;i<size;i++)
{
    int prev = A[i-1];
    int cur = A[i];

    if ( cur > prev )
    {
        // make new fence and push stack
        B[i_prev] = fence_pos;
        fence_pos = i_prev;
        fence_val = prev;
    }
    else
    {
        // descending, cur is good :
        B[i_prev] = i;

        while( cur < fence_val )
        {
            prev_fence = B[fence_pos];
            B[fence_pos] = i;
            fence_pos = prev_fence;
            if ( fence_pos == -1 )
            {
                fence_val = -1;
                break;
            }
            fence_val = A[fence_pos];
        }
    }
}

This is useful in string matching, as we will see forthwith.

9/27/2011

09-27-11 - String Match Stress Test

Take a decent size file like "book1" , do :

copy /b book1 + book1 twobooks

then test on "twobooks".

There are three general classes of how string matchers respond to a case like "twobooks" :

1. No problemo. Time per byte is roughly constant no matter what you throw at it (for both greedy and non-greedy parsing). This class is basically only made up of matchers that have a correct "follows" implementation.

2. Okay with greedy parsing. This class craps out in some kind of O(N^2) way if you ask them to match at every position, but if you let them do greedy matching they are okay. This class does not have a correct "follows" implementation, but does otherwise avoid O(N^2) behavior. For example MMC seems to fall into this class, as does a suffix tree without "follows".

Any matcher with a small constant number of maximum compares can fall into this performance class, but at the cost of an unknown amount of match quality.

3. Craps out even with greedy parsing. This class fails to avoid O(N^2) trap that happens when you have a long match and also many ways to make it. For example simple hash chains without an "amortize" limit fall in this class. (with non-greedy parsing they are O(N^3) on degenerate cases like a file that's all the same char).


Two other interesting stress tests I'm using are :

Inspired by ryg, "stress_suffix_forward" :

4k of aaaaa...
then paper1
then 64k of aaaa...
obviously when you first reach the second part of "aaaa..." you need to find the beginning of the file, but a naive suffix sort will have to look through 64k of following a's before it finds it.

Another useful one to check on the "amortize" behavior is "stress_search_limit" :

book1
then, 1000 times :
  128 random bytes
  the first 128 bytes of book1
book1 again
obviously when you encounter all of book1 for the second time, you should match the whole book1 at the head of the file, but matchers which use some kind of simple search limit (eg. amortized hashing) will see the 128 byte matches first and may never get back to the really long one.

09-27-11 - God Damn It

When you are drilling a hole in a wood cabinet, first of all, just stop, don't fucking do it. But if you insist on continuing, god damn it make it centered and level and straight and all that.

If you're nailing or screwing into the exterior wood of a house, again, just stop. Do you really need to put screws in to hang your fucking garden party lights? No, I don't think you do. But if you insist, fucking caulk them or something so you aren't just piercing the waterproof skin and providing no protection.

If you're cutting a hole all the way through a roof or a wall to put a vent, fucking stop for a second and make sure you're doing it in the right place, make it level and centered.

You can't fucking undo these things.

09-27-11 - S2000 Prices

No surprise - S2000's have held their value very very well. For one thing, they're pretty rare, for another, they're great, and most importantly, they're a Honda, from the tail end of the glory days, when Honda was just giving away massive amounts of value. Honda was making $50k cars and selling them for $25k.

(aside : there's some sort of vague sense in which I believe Honda from somethinge like the mid-80's to the mid 90's made the greatest cars of all time; obviously not in terms of actually comparing them to modern cars, so that forces me to qualify it as "compared to their era" and then you get some moron who says the dupendinger hummdorf from 1910 was a bigger improvement over its era, which, okay, I have no fucking idea if that's true or not, and I don't care (and I doubt it), so I hate all that "good for its time" kind of rating. But anyway, when you look at the line from the CRX, the NSX, all the Type-R cars, just staggeringly good, so well made, reliability, perfectly tuned to give the driver the feedback and control he needs, and way way underpriced, so much more car for the money than the competition; it's a damn shame that that time is passed)

On the other hand, RX8 prices are falling fast, and something like a 2007 RX8 for $15k is looking pretty attractive -

Sometimes I go off on these flights of fancy about getting a 240Z or an E30 M3 or some cool old car like that, for the wonderful analog-ness of it, the lack of driver aids, light weight, direct steering. But when you can get an RX8 for the same price, come on, it's just better, much better. And then you don't have to deal with it being in the shop all the time. I like cars and all, but my tolerance for dealing with mechanics is very close to zero.

9/26/2011

09-26-11 - Tiny Suffix Note

Obviously there are lots of analogies between suffix tries and suffix arrays.

This old note about suffix arrays which provides O(N) neighbor pair match lengths is exactly analogous to using "follow pointers" for O(N) string matching in suffix tries.

(their paper also contains a proof of O(N)'ness , though it is obvious if you think about it a bit; see comments on previous post about this).

Doing Judy-ish stuff for a suffix tree is exacly analogous to the "introspective" stuff that's done in good suffix array sorters like divsufsort.

By Judy-ish I mean using a variety of tree structures and selecting one for the local area based on its properties. (eg. nodes with > 100 children switch to just using a radix array of 256 direct links to kids).

Suffix tries are annoying because it's easy to slide the head (adding nodes) but hard to slide the tail (removing nodes). Suffix arrays are even worse in that they don't slide at all.

The normal way to adapt suffix arrays to LZ string matching is just to use chunks of arrays (possibly a power-of-2 cascade). There are two problems I haven't found a good solution to. One is how to look up a string in the chunk that it is not a member of (eg. a chunk that's behind you). The other is how to deal with offsets that are in front of you.

If you just put your whole file in one suffix array, I believe that is unboundedly bad. If you were allowed to match forwards, then finding the best match would be O(1) - you only have to look at the two slots before you and after you in the sort order. But since we can't match forward, you have to scan. The pseudocode is like this :


do both forward and backward :
start at the sort position of the string I want to match
walk to the next closest in sort order (this is an O(1) table lookup)
if it's a legal match (eg. behind me) - I'm done, it's the best
if not, keep walking

the problem is the walk is unbounded. When you are somewhere early in the array, there can be an arbitrary number (by which I mean O(N)) of invalid matches between you and your best match in the sort order.

Other than these difficulties, suffix arrays provide a much simpler way of getting the advantages of suffix tries.

Suffix arrays also have implementation advantages. Because you separate the suffix string work from the rest of your coder it makes it easier to optimize each one in isolation, you get better cache use and better register allocation. Also, the suffix array can use more memory during the sort, or use scratch space, while a trie has to hold its structure around all the time. For example some suffix sorts will do things like use a 2-byte radix in parts of the sort where that makes sense (and then they can get rid of it and use it on another part of the sort), and that's usually impossible for a tree that you're holding in memory as you scan.

9/25/2011

09-25-11 - More on LZ String Matching

This might be a series until I get angry at myself and move on to more important todos.

Some notes :

1. All LZ string matchers have to deal with this annoying problem of small files vs. large ones (and small windows vs large windows). You really want very different solutions, or at least different tweaks. For example, the size of the accelerating hash needs to be tuned for the size of data or you can spend all your time initializing a 24 bit hash to find matches in 10 byte file.

2. A common trivial case degeneracy is runs of the same character. You can of course add special case handling of this to any string matcher. It does help a lot on benchmarks of course, because this case is common, but it doesn't help your worst case in theory because there are still bad degenerate cases. It's just very rare to have long degenerate matches that aren't simple runs.

One easy way to do this is to special case just matches that start with a degenerate char. Have a special index of [256] slots which correspond to starting with >= 4 of that char.

3. A general topic that I've never seen explored well is the idea of approximate string matching.

Almost every LZ string matcher is approximate, they consider less than the full set of matches. Long ago someone referred to this as "amortized hashing" , which refers to the specific implemntation of a hash chain (hash -> linked list) in which you simply stop searching after visiting some # of links. (amortize = minimize the damage from the worst case).

Another common form of approximate string searching is to use "cache tables" (that is, hash tables with overwrites). Many people use a cache tables with a few "ways".

The problem with both these approaches is that the penalty is *unbounded*. The approximate match can be arbitrarily worse than the best match. That sucks.

What would be ideal is some kind of tuneable and boundable approximate string match. You want to set some amount of loss you can tolerate, and get more speedup for more loss.

(there are such data structures for spatial search, for example; there are nice aproximate-nearest-neighbors and high-dimensional-kd-trees and things like that which let you set the amount of slop you tolerate, and you get more speedup for more slop. So far as I know there is nothing comparable for strings).

Anyhoo, the result is that algorithms with approximations can look very good in some tests, because they find 99% of the match length but do so much faster. But then on another test they suddenly fail to find even 50% of the match length.

9/24/2011

09-24-11 - Suffix Tries 2

Say you have a suffix trie with path compression.

So, for example if you had "abxyz" , "abymn" and "abxyq" then you would have :


[ab]   (vertical link is a child)
|
[xy]-[ymn]  (horizontal link is a sibling)
|
z-q

only the first character is used for selecting between siblings, but then you may need to step multiple characters to get to the next branch point.

(BTW I just thought of an interesting alternative way to do suffix tries in a b-tree/judy kind of way. Make your node always have 256 slots. Instead of always matching the first character to find your child, match N. That way for sparse parts of the tree N will be large and you will have many levels of the tree in one 256-slot chunk. In dense parts of the tree N becomes small, down to 1, in which case you get a radix array). Anyhoo..

So there are substrings that don't correspond to any specific node. For example "abx" is between "ab" and "abxy" which have definite spots in the tree. If you want to add "abxr" you have to first break the "xy" and then add the new node.

Okay, this is all trivial and just tree management, but there's something interesting about it :

If you have a "follow" pointer and the length you want does not correspond to a specific node (ie it's one of those between lengths), then there can be no longer match possible.

So, you had a previous match of length "lastml". You step to the next position, you know the best match is at least >= lastml-1. You use a follow pointer to jump into the tree and find the node for the following suffix. You see that the node does not have length "lastml-1", but some other length. You are done! No more tree walking is needed, you know the best match length is simply lastml-1.

Why is this? Consider if there was a longer match possible. Let's say our string was "sabcdt..." at the last position we matched 5 ("sabcd"). So we now have "abcdt..." and know match is >= 4. We look up the follow node for "abcd" and find there is no length=4 node in the tree. That means that the only path in the tree had "dt" in it - there has been no character other than "t" after "d" or there would be a branching node there. But I know that I cannot match "t" because if I did then the previous match would have been longer. Therefore there is no longer match possible.

This turns out to be very common. I'm sure if I actually spent a month or so on suffix tries I would learn lots of useful properties (there are lots of papers on this topic).

09-24-11 - Suffix Tries 1

To make terminology clear I'm going to use "trie" to mean a tree in which as you descend the length of character match always gets longer, and "suffix trie" to indicate the special case where a trie is made from all suffixes *and* there are "follow" pointers (more on this later).

Just building a trie for LZ string searching is pretty easy. Using the linked-list method (which certainly has disadvantages), internal nodes only need a child & sibling pointer, and some bit of data. If you always descend one char at a time that data is just one char. If you want to do "path compression" (multi-char steps in a single link) you need some kind of pointer + length.

(it's actually much easier to write the code with path compression, since when you add a new string you only have to find the deepest match in the tree then add one node; with single char steps you may have to add many nodes).

So for a file of length N, internal nodes are something like 10 bytes, and you need at most N nodes. Leaves can be smaller or even implicit.

With just a normal trie, you have a nice advantage for optimal parsing, which is that when you find the longest match, you also automatically walk past all shorter matches. At each node you could store the most recent position that that substring was seen, so you can find the lowest offset for each length of match for free. (this requires more storage in the nodes plus a lot more memory writes, but I think those memory writes are basically free since they are to nodes in cache anyway).

The Find and Insert operations are nearly identical so they of course should be done together.

A trie could be given a "lazy update". What you do is on Insert you just tack the nodes on somewhere low down in the tree. Then on Find, when you encounter nodes that have not been fully inserted you pick them up an carry them with you as you descend. Whenever you take a path that your baggage can't take, you leave that baggage behind. This could have advantages under certain usage patterns, but I haven't actually tried it.

But it's only when you get the "follow" pointers that a suffix trie really makes a huge difference.

A follow pointer is a pointer in the tree from any node (substring) to the location in the tree of the substring without the first character. That is, if you are at "banana" in the tree, the follow pointer should point at the location of "anana" in the tree.

When you're doing LZ compression and you find a match at pos P of length L, you know that at pos P+1 there must be a match of at least length L-1 , simply by using the same offset and matching one less character. (there could be a longer match, though). So, if you know the suffix node that was used to find the match of length L at pos P, then you can jump in directly to match of length L-1 at the next position.

This is huge. Consider for example the fully degenerate case, a file of length N of all the same character. (yes obviously there are special case solutions to the fully degenerate case, but that doesn't fix the problem, it just makes it more complex to create the problem). A naive string matcher is actually O(N^3) !!

For each position in the file (*N)
Consider all potential matches (*N)
Compare all the characters in that potential match (*N)
A normal trie makes this O(N^2) , because the comparing characters in the string is combined with finding all potential matches, so the tree descent + string compares combined are just O(N).

But a true suffix trie with follow pointers is only O(N) for the whole parse. Somewhere early on would find a match of length O(N) and then each subsequent one just finds a match of L-1 in O(1) time using the follow pointer. (the O(N) whole parse only works if you are just finding the longest length at each position; if you are doing the optimal parse where you find the lowest offset for each length it's O(N^2))

Unfortunately, it seems that when you introduce the follow pointer this is when the code for the suffix trie gets rather tricky. It goes from 50 lines of code to 500 lines of code, and it's hard to do without introducing parent pointers and lots more tree maintenance. It also makes it way harder to do a sliding window.

9/23/2011

09-23-11 - Morphing Matching Chain

"MMC" is a lazy-update suffix tree.

mmc - Morphing Match Chain - Google Project Hosting
Fast Data Compression MMC - Morphing Match Chain
Fast Data Compression BST Binary Search Tree
encode.ru : A new match searching structure
Ultra-fast LZ

(I'm playing a bit loose with the term "suffix tree" as most people do; in fact a suffix tree is a very special construction that uses the all-suffixes property and internal pointers to have O(N) construction time; really what I'm talking about is a radix string tree or patricia type tree). (also I guess these trees are tries)

Some background first. You want to match strings for LZ compression. Say you decide to use a suffix tree. At each level of the tree, you have already matched L characters of the search string; you just look up your next character and descend that part of the tree that has that character as a prefix. eg. to look up string str, if you've already decended to level L, you find the child for character str[L] (if it exists) and descend into that part of the tree. One way to implement this is to use a linked list for all the characters that have been seen at a given level (and thus point to children at level +1).

So your nodes have two links :


child = subtree that matches at least L+1 characters
sibling = more nodes at current level (match L characters)

the tree for "bar","band",bang" looks like :

b
|  (child links are vertical)
a
|
r-n  (sibling links are horizontal)
| |
* d-g
  | |
  * *

where * means leaf or end of string (and is omitted in practice).

Okay, pretty simple. This structure is not used much in data compression because we generally want sliding windows, and removal of strings as they fall out of the sliding window is difficult.

(Larsson and others have shown that it is possible to do a true sliding suffix tree, but the complexity has prevented use in practice; this would be a nice project if someone wants to make an actual fast implementation of the sliding suffix trie)

Now let's look at the standard way you do a hash table for string matching in the LZ sliding window case.

The standard thing is to use a fixed size hash to a linked list of all strings that share that hash. The linked list can just be an array of positions where that hash value last occured. So :


pos = hashTable[h] contains the position where h last occured
chain[pos] contains the lat position before pos where that same hash h occurred

the nice thing about this is that chain[] can just be an array of the size of the sliding window, and you modulo the lookup into it. In particular :

//search :
h = hash desired string
next = hashTable[h];
while ( next > cur - window_size )
{
  // check match len of next vs cur
  next = chain[next & (window_size-1) ];
}

note that the links can point outside the sliding window (eg. either hashTable[] or chain[] may contain values that go outside the window), but we detect those and know our walk is done. (the key aspect here is that the links are sorted by position, so that when a link goes out of the window we are done with the walk; this means that you can't do anything like MTF on the list because it ruins the position sort order). Also note that there's no check for null needed because we can just initial the hash table with a negative value so that null is just a position outside the window.

To add to the hash table when we slide the window we just tack onto the list :


// add string :
chain[ cur & (window_size)-1 ] = hashTable[h];
hashTable[h] = cur;

and there's the sort of magic bit - we also removed a node right there. We actually popped the node off the back of the sliding window. That was okay because it must have been the last node on its list, so we didn't corrupt any of our lists.

That's it for hash-chain review. It's really nice how simple the add/remove is, particularly for "Greedy" type LZ parsers where you do Insert much more often than you do Find. (there are two general classes of LZ parers - "Optimal" which generally do a Find & Insert at every position, and "Greedy" which when they find a match, step ahead by the match len and only do Inserts).

So, can we get the advantages of hash chains and suffix trees?

Well, we need another idea, and that is "lazy updates". The idea is that we let our tree get out of sorts a bit, and then fix it the next time we visit it. This is a very general idea and can be applied to almost any tree type. I think the first time I encountered it was in the very cool old SurRender Umbra product, where they used lazy updates of their spatial tree structures. When objects moved or spawned they got put on a list on a node. When you descend the tree later on looking for things, if a node has child nodes you would take the list of objects on the node and push them to the children - but then you only descend to the child that you care about. This can save a lot of work under certain usage patterns; for example if objects are spawning off in some part of the tree that you don't visit, they just get put in a high up node and never pushed down to the leaves.

Anyhoo, so our suffix tree requires a node with two links. Like the hash table we will implement our links just as positions :

struct SuffixNode { int sibling; int child; }
like the hash table, our siblings will be in order of occurance, so when we see a position that's out of the window we know we are done walking.

Now, instead of maintaining the suffix tree when we add a node, we're just going to tack the new node on the front of the list. We will then percolate in an update the next time we visit that part of the tree. So when you search the tree, you can first encounter some unmaintained nodes before you get to the maintained section.

For example, say we had "bar" and "band" in our tree, and we add "bang" at level 2 , we just stick it on the head and don't descend the tree to put it in the right place :


b
|  (child links are vertical)
a
|
NG-r-n  (sibling links are horizontal)
     |
     d

(caps indicates unmaintained portion)

now the next time we visit the "ba" part of the tree in a retrieval, we also do some maintenance. We remember the first time we see each character (using a [256] array), and if we see that same character again we know that it's because part of the tree was not maintained.

Say we come in looking for "bank". If see a node with an "n" (that's a maintained n) we know we are done and we go to the child link - there can't be any more n's behind that node. If we see an "N" (no child link), we remember it but we have to keep walking siblings. We might see more "N"s and we are done if we see an "n". Then we update the links. We remove the "n" (of band) from the sibling link and connect it to the "N" instead :


b
|  (child links are vertical)
a
|
n-r
|   
g---d

And this is the essence of MMC (lazy update suffix trie = LUST).

A few more details are significant. Like the simple hash chain, we always add nodes to the front of the list. The lazy update also always adds nodes to the head - that is, the branch that points to more children is always at the most recent occurance of that substring. eg. if you see "danger" then "dank" then "danish" you know that the "dan" node is either unmaintained, or points are the most recent occurance of "dan" (the one in "danish"). What this means is that the simple node removal method of the hash chain works - when the window slides, we just let nodes fall out of the range that we consider valid and they drop off the end of the tree. We don't have to worry about those nodes being an internal node to the tree that we are removing, because they are always the last one on a list.

In practice the MMC incremental update becomes complex because you may be updating multiple levels of the tree at once as you scan. When you first see the "NG" you haven't seen the "n" yet and you don't want to scan ahead the list right away, you want to process it when you see it; so you initially promote NG to a maintained node, but link it to a temporary invalid link that points back to the previous level. Then you keep walking the list and when you see the "n" you fix up that link to complete the maintenance.

It does appear that MMC is a novel and interesting way of doing a suffix trie for a sliding window.

9/22/2011

09-22-11 - Sports Car Tires

I fucking went through my rear tires already, in just about 1 year or about 8000 miles. It's somewhat common for modern 911's to wear out the inner edge of the rear tires very fast, because you run a lot of rear negative camber, they're heavy in the rear, and of course you tend to drive around like a maniac.

I of course knew that tires for this car would be a lot more expensive, but it's a bit more subtle than that. If you just look at tire prices you might think they are 2-4X more expensive. They aren't just 2X or 4X more expensive, they're actually something like 10X more expensive. Here's why :

1. Just the basic tire is something like 3X more expensive due to being a large/rare size. ($300 a tire instead of $100 a tire)

2. But you don't want to buy el cheapo tires like you did for your commuter car, you want some nice performance tires, right? So now we're talking 4-5X more expensive.

3. And you can't get those tires at Big O or Walmart or whatever, so you have to go to a specialty shop, so the install is more expensive.

4. But the biggest factor is that you go through them much much faster. For one thing, they're a poor-treadwear soft compound, but it's also just the driving style. You're literally "burning rubber" all the time, and if you like to go fool around and slide some drifts or donuts, that can

5. Driving street tires on the track can also wreck them in one session, because they can't handle the heat cycles; you'll literally get melted rubber, usually on the outside edges if you're cornering hard, and it can just come off in chunks. (obviously if you're serious you have special track tires and you expect to go through them fast, but some people are under the misconception that they can take their street car to the track once in a while and it will be okay; well, yeah, it will probably be okay, but it will cost a lot more than you think)

The result is that tires are costing me almost $2000/year, which is rather more than I expected.

(basically all the same things could be said for brakes, though they don't wear quite so fast, and track days and donuts don't destroy them as instantly as they destroy tires (on some cars track days can destroy brakes because they get too hot and you can crack pads or even wreck calipers, but Porsches have pretty good brake cooling))


Anyhoo. I'm getting mildly annoyed with the car. My tires are shot and I can't get replacements in for a week cuz they're rare and have to be ordered (I'm sure I could find them at some shop around town if I wanted to make a million phone calls).

It would be nice to have a car that you could just find parts for anywhere. That you could break down in the middle of the hick middle of the country and find a mechanic who could fix it. I like having a car that's fun to drive but I don't like having a car that's a prima donna.

One of the advantages of the Lotus line is that you can take them to a Toyota mechanic. I wrote a post once about how small-car-maker engine production is super retarded, but I think I didn't post it.

09-22-11 - Roku - Amazon Streaming

Not quite ready for prime time. Setup was real easy, that's good. But some things aren't quite right.

(tangential rant : why in the fuck do you bastards still make those fucking plugs with the DC box built onto the plug so that it blocks other outlets !? god dammit, you must know that it fucking sucks and you just don't give a shit. I have to run extension cords just to get the big plugs spaced out away from the power strip or UPS because they would all run into each other). (oh, and you fuckers can't decide if you want to put the protuberance on the side of the plugs or below the plugs, so no matter which way the power strip orients the plugs, there will be some fucking device that doesn't work with it)

(oh, and I decided not to get a Roku a few days ago because I don't want to buy more electronic shit for no good reason, but then I went on the PS3 to watch some Netflix and got the fucking "a system software update is needed" AGAIN; of course the fucking morons can't check that before you get into the Netflix app, so then you have to reboot back out to the dashboard, and they can't just fucking start the update for you then, you have to manually go fucking dig all over the massive convoluted menu to find it; the week before they logged me out of PSN to force me to agree to some new license agreement; WTF WTF have you got no concept of user experience? why are you morons all so bad at taking my money? the fucking plumber won't return my calls, fucking PS3 has chased me right off their console, wtf wtf).

1. The remote sucks balls. It's like a Fischer Price My First Remote. The buttons feel horrible, really stiff and clunky, and they're way too far apart from each other, so you can't just use one thumb and move it around without straining. The whole ergonomics of it are just awful. It has too much weight in the bottom which makes it take extra muscle to balance. The ok button should be in the middle of the arrows. It should be hourglass shaped. Fucking copy the Tivo remote god dammit.

2. Navigation on the Roku is super super slow. Hit "home" and wait, and wait, and wait, and wait. Okay, there it went. Of course it's better than going from PS3 Netflix to System Settings or something like that (which requires a reboot), and all these devices seem to be unreasonably slow (the god damn TiVo was always frustrating slow, especially because it was only slow because it was wasting time loading animations, fucking give me a "plain text" option so I can get god damn fast menus!). (* addendum : it seems to have sped itself up; maybe it was doing some background task? dunno; it's still not super fast but it's tolerable; some players seem to be faster than others, Amazon seems to be a particularly slow one).

3. Amazon streaming is just unusable. There's no "queue" type of thing where I can select a subset of stuff I want to watch from my computer, and then choose one of that subset from the Roku. This just makes the whole thing complete shit, because I'm not going to browse through a thousand titles with the fucking arrow buttons on the roku. Mouse and keyboard are good tools for browsing, fucking arrow buttons are not acceptable. (there is a sort of "queue" for things you purchase, just not for the free streaming stuff).

Oh well. Maybe if Amazon really does buy Netflix it will all be fixed.

What I really want is a premium subscription service to torrents. I'd like to pay $5 a month or something, and for that I get to choose what movies and TV shows I'd like, and some kid in Russia finds the best torrent for each movie and TV show and feeds them out to the subscribers. Obviously I can use EZRSS or something right now, but it's just flakey enough that I have to manage it by hand a lot, and I would pay to not have to do that.

9/21/2011

09-21-11 - Four Myths

I believe that the modern white middle-upper class male is highly susceptible to these four myths.

1. "Stay out of it". Politics is a mess. It's frustrating. It's largely controlled by corporate spending and the outrageous emotional ideology of fringe crackpots who scream on talk radio. What can you do about it? It's better just to stay out of it. Sure, Fox News is telling insane lies all the time and shouldn't be allowed to mascarade as news, but what can you do about it? Sure, Corporations should not be counted as people under the 1st ammendment. It's just too frustrating and gives us a headache and distracts from our work. So let's be good consumers and go back to arguing about universal remotes and make some more products that people don't need.

2. "Happiness". One of the great mythical movements of the last twenty years or so has been a sort of spiritual glorification of the pursuit of happiness. Atheists who are increasingly disillusioned with the idea of doing something "significant" with their lives are grasping for a central concept to build their lives around, and what they have found is "just be happy".

I believe this is worth restating. Human beings need to believe that their life is for something; that there is a purpose, something to base your actions on day to day, that you're not just ticking off time until you die. Modern ultra-rational man finds it hard to believe in the purposes of older days; obviously religion is out, but even things like "write the great American novel" or "make a difference in the world" are hard for cynical modern man to build his life around, because he starts thinking "what's the point of that really?", all it does is make other people like you, maybe it helps other people but what's the point of helping other people really? This reductivist reasoning can destroy any "life purpose". So after several crises, modern man finds "happiness". I should just do what makes me happy.

Now, the "happiness" pursuers don't just go and do drugs and party or whatever; if you are aware of the happiness movement at all, it's somewhat sophisicated in the sense that it is looking for longer term deeper happiness, which might come from connection to your community, or building something with your hands, or traveling somewhere you are a bit afraid to go, etc. But the reason for it at the core is not doing something for the world, it is entirely selfish.

Because this modern happiness movement is somewhat more sophisticated than plain old gluttony and self-indulgence, it can be a bit hard to see, but in fact it is still exactly what the ruling elite want you to do. They want you to focus on your self, not on the world around you. They want you to avoid difficulty that might make you unhappy. They certainly don't want people dedicating their lives to changing the world or making it a better place.

3. "Identity Liberty". There have been substantial political gains in individual liberties in the last forty years; and there is more freedom and acceptance of "alternative lifestyles" and identities. While this is good, and I don't want to diminish the importance of greater rights for The Gays or whatever, it is really a side issue that has taken center stage. When you ask a liberal how you think the world has done in the last 40 years, they will inevitably bring this up as the major positive.

The things is, the ruling elite really don't give a rats ass about "identity liberty". It's a distraction. It's a gladiator fight in the colliseum to keep the rabble occupied while they keep raping you. They don't give a shit about gays or abortion or any of that shit. They care about the structure of power. And while we are fighting about whether there should be a Native American monument at Little Big Horn they have been putting wall street bankers in power at Treasury, the SEC, Fannie, the Fed, etc. They have been giving corporations greater power than humans or countries via NAFTA, Citizens United, etc. There is no more check on executive power or journalistic oversight. The entire congressional law-making process has become a joke.

It's like we're squabbling over the 2 men from Australia and they've just locked up the 7 bonus armies from the Americas. The most important thing is the structure of power, because the capacity for liberty flows from that.

4. "Meritocracy".

bonus : 5. "Anti-unionism".

... I got bored of this post. I'm gonna go watch TV and drink beer. Rugby world cup is on, woot!

9/20/2011

09-20-11 - Sensory Pollution

My TV has a red light to indicate that it's OFF. Everything has lights to indicate they're on, including the power strips and UPS and such. The alarm sensors have a mess of lights.

Everything beeps when you press buttons. Gas air blower and lawn mower. Truck backing up, beep beep beep. Car alarms going off. Fucking beeps and honks when cars lock and unlock.

Fucking car headlights are way too bright. Some annoying cars now have this sparkle flashy thing when they brake.

It's an assault. Literally, it beats on your brain with a cudgel of "look at me!". No, god dammit, I want to look at what I choose to pay attention to.

9/19/2011

09-19-11 - Netflix Super-Self-Crapulation

Wow, great example of an "apology" that makes things so much worse. Paraphrase :

"We've listened to your complaints and decided that we don't give a shit, so we're going to continue in that vein even more! We will be going ahead with our corporate strategy to fuck you over; our long term plan to gradually phase out physical DVD's isn't going fast enough for our quarter-by-quarter stock growth expectations, oh and I'm going to do the massive-douche thing of pretending that fucking you over is somehow good for you".

Original :

I messed up. I owe you an explanation.

It is clear from the feedback over the past two months that many members felt we lacked respect and humility in the way we announced the separation of DVD and streaming and the price changes. That was certainly not our intent, and I offer my sincere apology. Let me explain what we are doing.

For the past five years, my greatest fear at Netflix has been that we wouldn't make the leap from success in DVDs to success in streaming. Most companies that are great at something � like AOL dialup or Bordeers bookstores � do not become great at new things people want (streeaming for us). So we moved quickly into streaming, but I should have personally given you a full explanation of why we are splitting the services and thereby increasing prices. It wouldn’t have changed the price increase, but it would have been the right thing to do.

So here is what we are doing and why.

Many members love our DVD service, as I do, because nearly every movie ever made is published on DVD. DVD is a great option for those who want the huge and comprehensive selection of movies.

I also love our streaming service because it is integrated into my TV, and I can watch anytime I want. The benefits of our streaming service are really quite different from the benefits of DVD by mail. We need to focus on rapid improvement as streaming technology and the market evolves, without maintaining compatibility with our DVD by mail service.

So we realized that streaming and DVD by mail are really becoming two different businesses, with very different cost structures, that need to be marketed differently, and we need to let each grow and operate independently.

It’s hard to write this after over 10 years of mailing DVDs with pride, but we think it is necessary: In a few weeks, we will rename our DVD by mail service to “Qwikster”. We chose the name Qwikster because it refers to quick delivery. We will keep the name “Netflix” for streaming.

Qwikster will be the same website and DVD service that everyone is used to. It is just a new name, and DVD members will go to qwikster.com to access their DVD queues and choose movies. One improvement we will make at launch is to add a video games upgrade option, similar to our upgrade option for Blu-ray, for those who want to rent Wii, PS3 and Xbox 360 games. Members have been asking for video games for many years, but now that DVD by mail has its own team, we are finally getting it done. Other improvements will follow. A negative of the renaming and separation is that the Qwikster.com and Netflix.com websites will not be integrated.

There are no pricing changes (we’re done with that!). If you subscribe to both services you will have two entries on your credit card statement, one for Qwikster and one for Netflix. The total will be the same as your current charges. We will let you know in a few weeks when the Qwikster.com website is up and ready.

For me the Netflix red envelope has always been a source of joy. The new envelope is still that lovely red, but now it will have a Qwikster logo. I know that logo will grow on me over time, but still, it is hard. I imagine it will be similar for many of you.

I want to acknowledge and thank you for sticking with us, and to apologize again to those members, both current and former, who felt we treated them thoughtlessly.

Both the Qwikster and Netflix teams will work hard to regain your trust. We know it will not be overnight. Actions speak louder than words. But words help people to understand actions.

Respectfully yours,

-Reed Hastings, Co-Founder and CEO, Netflix

p.s. I have a slightly longer explanation along with a video posted on our blog, where you can also post comments.

Lesson for myself :

Never ever NEVER put any work into a web site. Do not post to forums. Do not write reviews. Do not keep lists of movies. If you do not own the content, they will fuck you. Be it censorship (Yelp, Amazon, CNET), using your work for advertising profit (everyone), deleting your work or shutting down the site, introducing new "features" or revising the site in a way that breaks it, or just otherwise fucking you.

I know this, but I get sucked into thinking "oh it'll be fine, just this one time". It's also one of those things where everyone else is doing it, so I start to think "hmm maybe it's fine, maybe I'm being unreasonable". Nope. Everyone else is wrong. Make your own correct decision, and that is do not give control of your personal content to anyone else.

ADDENDUM :

Somehow I completely missed the fact that Amazon Prime subscribers get free streaming, just found out today (that's why it's occasionally useful to talk to other human beings). WTF Amazon, way to go informing me. You do a great job of letting me know about the fucking Amazon Visa that I don't want, but not this. Wow. And Roku streams Amazon Prime. Goodbye Netflix!

ADDENDUM 2 :

I'm surprised that a lot of people don't get why this is such a massive fuckup. The greatest asset that Netflix has is a large user base that has invested personal time into the site, writing reviews, tracking what movies they've seen and what they want to see. It's a "Yelp" or "Myspace" for movies. (they've already massively fucked up on this by failing to develop the community features and such, but whatever).

When they split the pricing earlier this year, it caused a lot of us to switch to streaming only, at which time we discovered that with streaming only you couldn't even *see* the movies that weren't available for streaming. That's such a massive fuckup right there. I should still be able to mark what movies I want to watch and which I have seen already. Having users on your site storing their movie-watching preferences is what gives you value. It's what makes them committed to your site.

Now completely splitting the streaming and non-streaming into two sites so that I no longer have one place to go and store my movie watching desires (and hopes and dreams).

ADDENDUM 3 : Netflix also silently deleted your "Saved" section of the Instant Queue recently. Hope you didn't have any data in there you wanted.

this comic is alright.

They're being so massively retarded that it has to be intentional. It makes me think this speculation might be true.

09-19-11 - Game Theory

When your opponent in poker is playing like an absolute moron, you don't think "god damn this guy", you think "how do I take advantage of it". If you don't want to be quite so callous, another way to say it is : you must accept the reality of the situation you are given, and then think how can you best act in that reality. You shouldn't stick to a plan (like playing straightforward tight poker) and think that the world should go along with your plan, just because you are doing things "right" (in the naive sense) doesn't mean the world is obligated to go along with it and let you win.

WA landlord-tenant law is absurdly pro-landlord. Response : don't rent, be a landlord. (CA and NY law is very pro-tenant, response is the opposite of course).

Landlords don't actually charge you enough for move-out deposit subtractions. I'm constantly pissed off by the fact that they charge me for bullshit that is totally inappropriate (like charging me for cleaning even after I've hired professional cleaners). The thing is, they might charge you the $150 cleaning fee, but they don't charge you $100 for the pain in the butt of hiring the cleaners and letting them in and out of the house. Response : don't clean your rentals, just pay the charge. (further response : don't agree to more than $500 or so security deposit)

Service men who work on plaster, fiberglass, or any of those other nasty toxic substances don't charge nearly enough for the trouble of it. They basically just charge normal low-skill labor rates, no extra fees for the life-shortening or discomfort. Response : never do this work yourself, never work with toxic substances, chemicals or fine particles, always hire someone else to do it.


Home maintenance is one of those unstable equilibria of implicit contract (like the "golden rule"). What I mean is, in home maintance you have two options :

1. Fix things properly so that they last. or 2. Fix things just well enough so that they will probably be okay for 5-10 years.

I'm really talking about things that are hard to go back and change later, that are much cheaper to do well when you have the chance. Like you have a wall open, do you use high quality studs and put in extra wiring so that you won't need to open it again later, or do you just do the minimum for the moment? Or you have the foundation exposed, do you just fill a crack with vinyl crack filler or really properly fix the foundation for the future? Or you're doing framing, do you use dense high-quality treated wood that will resist rot for a long time, or the cheapest wood that passes code?

Let us assume that over 50+ years, the more robust choice (#1) will be much better, but over 1-20 years, the cheap out choice will be better.

For you personally, chances are that the cheap-out way (#2) will be +EV , because chances are you won't live in the same house super long. But for society as a whole, if everyone did the #1 choice and fixed things properly, we would all be better off. You wouldn't come in to a home and find deferred maintenance and crappy short-term patches. Your good quality work might not pay off for you (because you move out), but the next person would inherit it, and you would inherit the good work they had done.

The problem is that cheating on the social constract is always +EV for you personally, though it may be -EV for the group.

A good example in poker arises when many pros are at a table with a whale. The most +EV way for the pros to play is to all mostly avoid each other and go after the whale, but don't make it super obvious, and don't do things that annoy him and might chase him away. But the problem is that for any one pro, you can in the short term (local maxima) increase your EV by also going after the other pros and by really baiting the whale, for example isolation raising big any time the whale enters the pot, and re-raising other people's light isolations. The problem is once all the pros start doing this, they wind up shutting the whale out of a lot of pots and playing too many pots just with each other, and the net EV of the pros goes way down.

9/15/2011

09-15-11 - Spray Park

Spray Park is one of those easily accessible and outrageously beautiful places that are a real bonus to living here. You hike through a bunch of typical northwest forest, up a decently hard hill, and then suddenly emerge into this sub-alpine meadow wonderland of little wild flower and new growth, backed by the giant mountain. Further up you can get into the true alpine barren lands, which are sort of calming in their emptiness. Eventually you get up into big snow fields, where I've seen the crazy outdoors people skiing in the middle of summer.

09-15-11 - DIY

I am so fucking sick of doing this shit, it's such a waste of time. I wish there people you could hire that would do this shit for you, but it just doesn't seem to exist. I thought I found the ideal thing - Seward Park Repairs , right in my neighborhood, just call them up they subcontract out and take care of whatever. (the biggest problem with hiring people to do shit is the amount of time it takes to find them and call them up and then vet them and so on). But then I found a forum post by the owner of Seward Park Repairs where he says it's okay to vent a bathroom exhaust fan into the attic. WTF David, if that's the kind of shoddy ass work you do, I'm glad I found out first. Wow, how are you people all so epically incompetent.

I really want a grounds manager to just take care of this shit for me. Higgins, this door is sticking, have someone take care of it, of course sir. I guess I need to make more money, but that's not possible as long I'm wasting all my time on fucking DIY bullshit!

There is this stupid dangerous machismo of "I could do that". Harrumph, I won't hire someone, I'm a man, I can do that myself. Of course other people will judge you and pressure you in this way as well; harrumph why'd you hire someone to put in that vent fan, can't you do that yourself? don't you have a penis?

Well, that's fucking stupid. Just because you *can* do something doesn't mean you should. Just because lots of stupid people think that it's admirable to do things yourself doesn't mean that it actually is.

What's admirable is making the right decision for yourself, regardless of what others think is right. This is obvious, but it's a very difficult way to actually live.

It would be so nice to be able to hire someone to take care of things and be able to trust that they will do a decent job. I don't even mean a builder, it could just be anyone off the street and they could subcontract everything. All they have to be able to do is basic research and decision making and phone calls. Unfortunately that takes a ton of intelligence and is very hard to find. It's hard to find even among highly skilled programmers.

A crucial aspect is the "what needs approval" question. You need an employee who has the sense to know what they should ask you about, and what they should just decide themselves and not bug you. Both ways of getting it wrong are bad; you don't want someone who just goes off and makes a bunch of decisions and you find out too late that you got the gold-plated Versace bathroom set ; but you also don't want someone who comes to you every five minutes with every question. The vast majority of programmers I've worked with fall towards one or the other side; it's very rare when you find someone who has that sense of judgement to know hey this is important I better ask about it, or hey I should just keep on trucking and make my own call on this.

I have a whole rant percolating about how shockingly hard it is to find what I consider "basic professionalism". You want to know why you're all out of work? When you get a business call, return it right away. When you have an appointment, make it, and if you can't then you call and tell them you'll be late *before* the appointment time. When you say that you will do something, you fucking get it done or you let them know very early on that you can't do it. If you are given a task that you don't know how to do right, you say so, you don't just try to fake it and fuck it up.

9/11/2011

09-11-11 - Shitty Product Design

I feel like a lot of "design" is making product worse. With lots of products there is a well known good way to make them, just fucking leave it alone, stop changing things for no good reason, you're fucking them up.

A good example are "stemless wine glasses". Uh, WTF, you moron, the stem is there for a reason. You just made it look trashy and made it much worse. Oh yes, I want finger prints on my wine glass. Yes, I love to warm up my wine when I hold it. Oh yes, I don't want to be able to hold it up to the light properly.

(Classic designs are not always right though. I really don't see the point to double hung sash windows. Why in the fuck do I need to be able to open the top part? When do you want the top sash open and the bottom closed that you couldn't just have the bottom open instead? In my experience with these fuckers, the only thing the top sash is good for is letting in massive air leaks, or falling down slightly and getting stuck and being incredibly hard to slide back up because it has no handles or anything.)

And now for a photo tour of horrible designs around my home :

Pushing a window open with my hand was much too difficult. It only took a second and was easily adjustable, but I had to lean over. I'd much rather crank on this fucking floppy handle for five minutes. The result is that sometimes I want the window open but I just can't be bothered to take the time to crank it a million times, so I just open another window that isn't on a "convenient" crank.

These kind of faucets are horrible in many ways. The mode clicker at the end is always flakey (this one happens to work mostly), the fucking retractable head is totally unnecessary and just makes it wobbly and lower flow, but worse of all is the fucking joystick water control. It makes precisely setting the flow volume and temperature almost impossible. The variant of the joystick which pervades cheap hotel showers is the real pinnacle of shitty water control design. Fucking hot/cold knobs worked great. They're easy to adjust precisely, they hold their position and can't be easily bumped into scalding or freezing, they aren't fighting gravity so they don't slip. If you really want to change it would could do flow & temperature knobs, but don't fucking abandon the two-knob design! Knobs are perfect! I think water control peaked when the two faucets for hot and cold got combined into one faucet, but you still had the two knobs, it's been down-hill ever since.

I've done this one before, but it was in my sight so let's do it again. The Melitta single cup dripper is such a clear case of taking a near-perfect product that does the task it is designed for, and just fucking it up for no reason. (the only thing I would change about the original single cup dripper is I'd make it a bit bigger, because I like to use an obscene unreasonable amount of grounds for one cup of coffee).

Product designer : Why would anyone want to grab a drawer handle from above? I know, let's seal off the top and make a big surface to get dirty!

Quick - find the Stop button. Too late, your burrito exploded. Thank god for the "vegetable" feature. I'm sure glad there's a "hold warm" and "light timer" feature. And WTF is "cook" ? I bet they could cram some more buttons on there and it would be even more deluxe.

You could do the stop button test again. Think about how much your hand has to move around the panel just to set it to bake at 350. There's just no fucking thought about usability. Touch pads like this in general are just horrible interface devices, and sadly are getting more and more common (see for example washer/dryer rant). Two knobs is the perfect interface for an oven. One for temperature and one for function (off/bake/broil) (physical radio buttons would also be okay for function).

WTF are you product designers thinking? Do you actually think you're doing good work? You're not. You're making shit worse. You should be ashamed. You should feel humiliated and miserable every day at work as you take good products and make them trendy or "modernize" them or make them slightly cheaper to mass produce.

There needs to be something like a hippocratic oath for product designers ; "First, don't make it worse".

09-11-11 - Walk to the Lake

In pictures :

Discovered this hole in my bathroom ceiling. The gray at the top is the bottom of the upstairs bathtub, so I assume this was a water overflow that soaked through, so they just cut out the rotten bits all the way through three layers of floor. So that was most of a day wasted fixing this, and then repainting the ceiling. The worst part was that the hole they cut was a ragged mess so I had to square it up, and the ceiling is old plaster and lathe which is a pain in the ass to cut cleanly.

Leaving home now. Back yard is a nice place to sit. It's great to be able to walk down to the lake at the end of a long hot day of breathing plaster dust and paint fumes.

Fucking neighbor is running a drain pipe from his gutter onto my property. More annoying shit to deal with.

I feel like the blackberries have been especially good this year. Maybe it's just because I've moved to an area that has a lot more wild land than Cap Hill. In Seattle if you ignore a patch of land for a few minutes it becomes instantly covered in black berries. There's a pretty good patch of blackberries on almost every block around here, so you can take a stroll and snack as you go. I love just the smell of them, they make the air sweet and rich. I love how they come ripe at different times based on sun exposure and microclimate, so that the ripe season lasts over a month, you just pick from different sides of the block.

One of the trees on my parking strip is growing into the power lines. In Seattle it's the home owner's responsibility to keep their trees out of the lines. Texas and CA are not like that, the city or power company does it. Seattle also has no street sweeping (except right down town). And there are very few street lights (home owners are suggested to have a bright porch light).

On the way down to the lake now; there's been this congregation of sail boats next to I-90 almost every day this summer.

My local swim spot. Nice and un-crowded. Unfortunately there's also a sewage pipe near here (there seems to be one at almost every swim spot, including the official ones with life guards, I'm not quite sure why that is, I guess there's a mutual correlation that swim spots and sewer lines both tend to be on large patches of public land). ( see here for map )

old rants