cbloom rants

01-09-12 - LZ Optimal Parse with A Star Part 5

2012-01-09T16:51:00.001-08:00

Wrapping up the series with lots of numbers.

Previous parts :

cbloom rants 12-17-11 - LZ Optimal Parse with A Star Part 4
cbloom rants 12-17-11 - LZ Optimal Parse with A Star Part 3
cbloom rants 12-17-11 - LZ Optimal Parse with A Star Part 2
cbloom rants 10-24-11 - LZ Optimal Parse with A Star Part 1

I'm delirious with fever right now so I might write something inane, but I'm so bored of lying in bed so I'm trying to wrap this up. Anyhoo..

So first of all we have to talk a bit about what we're comparing the A Star parse to.

"Normal" is a complex forward lazy parse using heuristics to guide parsing, as described in Part 1. "Fast" is like Normal but uses simpler heuristics and simpler match finder.

"Chain" is more interesting. Chain is a complex "lazy"-type parser which considers N decisions ahead (eg. Chain 4 considers 4 decisions ahead). It works thusly :

Chain Parse : first do a full parse of the file using some other parser; this provides with a baseline cost to end from each point. Now do a forward parse. At each position, consider all match and literal options. For each option, step ahead by that option and consider all the options at the next position. Add up the cost of each coding step. After N steps (for chain N) add on the cost to end from the first baseline parse. Go back to the original position and finalize the choice with the lowest cost. Basically it's a full graph walk for N steps, then use an estimate of the cost to the end from the final nodes of that sub-graph.

To make Chain parsing viable you have to reduce the number of match options to a maximum of 8 or so. Still Chain N has a complexity of 8^N , so it becomes slow very quickly as N grows.

Chain forward parse is significantly better than LZSS style backwards optimal parse for these LZ coders that have important adaptive state. The baseline parse I use for Chain actually is a backwards LZSS optimal parse, so you can see how it does by looking at the "Chain 0" results.

First overall results. Chain 6 is the most amount of steps I can run in reasonable time, and AStar 2048 means the quantum length for dividing up the file for AStar was 2048.

	raw	Fast	Normal	Chain 6	AStar 2048
lzt00	16914	5179	5016	4923	4920
lzt01	200000	198313	198321	198312	198312
lzt02	755121	181109	177792	173220	173315
lzt03	3471552	1746443	1713023	1698949	1690655
lzt04	48649	13088	12412	10407	10249
lzt05	927796	368346	367598	355804	354230
lzt06	563160	352827	351051	344721	343173
lzt07	500000	226533	215996	209133	208566
lzt08	355400	250503	249987	230541	230220
lzt09	786488	302927	287479	268544	265525
lzt10	154624	11508	10958	10307	10291
lzt11	58524	20553	19628	19139	19087
lzt12	164423	29001	26488	23966	23622
lzt13	1041576	935484	931415	924510	922745
lzt14	102400	47690	47298	46417	46350
lzt15	34664	10832	10688	10269	10260
lzt16	21504	10110	10055	9952	9927
lzt17	53161	19526	18514	17971	17970
lzt18	102400	64280	63251	59772	59635
lzt19	768771	322951	288872	269132	269162
lzt20	1179702	888881	872315	856369	855588
lzt21	679936	91677	88011	83529	83184
lzt22	400000	287715	284378	279674	279459
lzt23	1048576	807253	804048	798369	798334
lzt24	3471552	1418076	1411387	1399197	1388105
lzt25	1029744	113085	107882	97320	100175
lzt26	262144	212445	210836	207701	207552
lzt27	857241	237253	235137	222023	220837
lzt28	1591760	332660	308940	260547	252808
lzt29	3953035	1193914	1180823	1147160	1135603
lzt30	100000	100001	100001	100001	100001
		10800163	10609600	10337879	10289860

Now number of Chain steps for the chain parser : (that's O0 - O6)

	U	N	O0	O1	O2	O3	O4	O5	O6
lzt00	16914	5016	5024	4922	4922	4922	4922	4923	4923
lzt01	200000	198321	198321	198312	198312	198312	198312	198312	198312
lzt02	755121	177792	177877	175905	174835	174073	173759	173509	173220
lzt03	3471552	1713023	1712337	1704417	1703873	1702651	1701635	1700282	1698949
lzt04	48649	12412	11315	10516	10481	10457	10427	10416	10407
lzt05	927796	367598	368729	365743	364332	360630	356403	355968	355804
lzt06	563160	351051	350995	346856	345500	344778	344739	344702	344721
lzt07	500000	215996	215644	211336	209481	209259	209244	209138	209133
lzt08	355400	249987	249372	239375	237320	231554	231435	233324	230541
lzt09	786488	287479	284875	280683	275679	270721	269754	269107	268544
lzt10	154624	10958	10792	10367	10335	10330	10311	10301	10307
lzt11	58524	19628	19604	19247	19175	19225	19162	19159	19139
lzt12	164423	26488	25644	24217	24177	24094	24108	24011	23966
lzt13	1041576	931415	931415	929713	927841	926162	924515	924513	924510
lzt14	102400	47298	47300	46518	46483	46461	46437	46429	46417
lzt15	34664	10688	10656	10317	10301	10275	10278	10267	10269
lzt16	21504	10055	10053	9960	9966	9959	9952	9948	9952
lzt17	53161	18514	18549	17971	17970	17974	17971	17973	17971
lzt18	102400	63251	63248	59863	59850	59799	59790	59764	59772
lzt19	768771	288872	281959	277661	273316	269157	269141	269133	269132
lzt20	1179702	872315	872022	868088	865376	863236	859727	856408	856369
lzt21	679936	88011	88068	84848	83851	83733	83674	83599	83529
lzt22	400000	284378	284297	281902	279711	279685	279689	279696	279674
lzt23	1048576	804048	804064	802742	801324	799891	798367	798368	798369
lzt24	3471552	1411387	1410226	1404736	1403314	1402345	1401064	1400193	1399197
lzt25	1029744	107882	107414	99839	100154	99710	98552	98132	97320
lzt26	262144	210836	210855	207775	207763	207738	207725	207706	207701
lzt27	857241	235137	236568	233524	228073	223123	222884	222540	222023
lzt28	1591760	308940	295072	286018	276905	273520	269611	264726	260547
lzt29	3953035	1180823	1183407	1180733	1177854	1170944	1162310	1152482	1147160
lzt30	100000	100001	100001	100001	100001	100001	100001	100001	100001
		10609600	10585703	10494105	10448475	10404719	10375899	10355030	10337879

Some notes : up to 6 (the most I can run) more chain steps is better - for the sum, but not for all files. In some cases, more steps is worse, which should never really happen, but it's an issue of approximate optimal parsers I'll discuss later. (*)

On most files, going past 4 chain steps helps very little, but on some files it seems to monotonically keep improving. For example lzt29 stands out. Those files are ones that get helped the most by AStar.

Now the effect on quantum size on AStar. In all cases I only output codes from the first 3/4 of each quantum.

	raw	256	512	1024	2048	4096	8192	16384
lzt00	16914	4923	4923	4920	4920	4920	4921	4921
lzt01	200000	198312	198312	198312	198312	198312	198314	198314
lzt02	755121	175242	173355	173368	173315	173331	173454	173479
lzt03	3471552	1699795	1691530	1690878	1690655	1690594	1690603	1690617
lzt04	48649	10243	10245	10234	10249	10248	10241	10241
lzt05	927796	357166	354629	354235	354230	354233	354242	354257
lzt06	563160	346663	343202	343139	343173	343194	343263	343238
lzt07	500000	209934	208669	208584	208566	208556	208553	208562
lzt08	355400	228389	229447	229975	230220	230300	230374	230408
lzt09	786488	266571	265564	265487	265525	265559	265542	265527
lzt10	154624	10701	10468	10330	10291	10273	10273	10272
lzt11	58524	19139	19123	19096	19087	19085	19084	19084
lzt12	164423	23712	23654	23616	23622	23628	23630	23627
lzt13	1041576	923258	922853	922747	922745	922753	922751	922753
lzt14	102400	46397	46364	46351	46350	46350	46348	46350
lzt15	34664	10376	10272	10260	10260	10251	10258	10254
lzt16	21504	9944	9931	9926	9927	9927	9927	9927
lzt17	53161	17937	17970	17968	17970	17969	17969	17969
lzt18	102400	59703	59613	59632	59635	59637	59640	59640
lzt19	768771	269213	269151	269128	269162	269193	269218	269229
lzt20	1179702	855992	855580	855478	855588	855671	855685	855707
lzt21	679936	83882	83291	83215	83184	83172	83171	83169
lzt22	400000	279803	279368	279414	279459	279605	279630	279647
lzt23	1048576	798325	798319	798321	798334	798354	798357	798358
lzt24	3471552	1393742	1388636	1388031	1388105	1388317	1388628	1388671
lzt25	1029744	97910	101246	101302	100175	100484	100272	100149
lzt26	262144	207779	207563	207541	207552	207559	207577	207576
lzt27	857241	222229	220832	220770	220837	220773	220756	220757
lzt28	1591760	256404	253257	252933	252808	252737	252735	252699
lzt29	3953035	1136193	1135442	1135543	1135603	1135710	1135689	1135713
lzt30	100000	100001	100001	100001	100001	100001	100001	100001
		10319878	10292810	10290735	10289860	10290696	10291106	10291116

The best sum is at 2048, but 1024 is a lot faster and almost the same.

Again, as the previous note at (*), we should really see just improvement with larger quantum sizes, but past 2048 we start seeing it go backwards in some cases.

Lastly a look at where the AStar parse is spending its time. This is for a 1024 quantum.

The x axis here is the log2 of the number of nodes visited to parse a quantum. So, log2=20 means a million nodes were needed to parse that quantum. So for speed purposes a cell one to the right is twice as bad. The values in the cells are the percentage of quanta in the file that needed that number of nodes.

(note : log2=20 means one million nodes were visited to output 768 bytes worth of codes, so it's quite a lot)

log2	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
lzt00	0	0	0	18.18	59.09	18.18	4.55
lzt01	3.75	0.75	41.2	34.08	13.86	5.62	0.75
lzt02	1.81	1.36	25.37	34.09	13.59	13.02	8.15	1.93	0.23	0.23
lzt03	1.46	1.18	17.51	18.46	14.16	13.17	6.95	4.81	3.66	4.81	9.54	2.79	0.96	0.11	0.03
lzt04	1.67	0	0	1.67	0	21.67	5	18.33	3.33	10	16.67	16.67	5
lzt05	0.59	0.25	4.41	10.77	9.92	18.32	13.23	10.09	9.67	6.02	12.47	3.22	0.51	0.08	0.08
lzt06	0.8	0.93	6.81	23.77	14.69	16.96	21.09	11.48	2.67	0.8
lzt07	0.46	0.46	8.66	7.88	6.8	15.3	17	14.53	5.56	9.58	8.19	4.79	0.31	0.31
lzt08	0	0	0	0	0	0	1.68	1.68	1.47	27.67	53.88	11.95	1.68
lzt09	0.29	0.48	0.76	0.86	0.95	3.9	28.07	47.76	16.18	0.38
lzt10	0	0.56	10.17	12.99	9.04	9.04	10.17	41.24	4.52	0.56	1.13
lzt11	0	0	7.89	10.53	14.47	17.11	6.58	9.21	21.05	10.53	2.63
lzt12	0	0	0	0	0	4.27	28.91	59.24	7.58
lzt13	0	0	0.07	0.14	0.57	1.72	3.36	5.72	39.24	42.03	7.08	0.07
lzt14	0	0.83	0	2.5	8.33	34.17	42.5	5	2.5	1.67	0.83	0	0.83
lzt15	0	2.27	4.55	15.91	13.64	15.91	13.64	6.82	11.36	11.36	4.55
lzt16	0	0	3.57	0	14.29	42.86	32.14	3.57
lzt17	1.39	1.39	2.78	1.39	4.17	75	13.89
lzt18	0	0	0	0	0	0.72	0	2.17	2.9	11.59	56.52	23.19	2.9
lzt19	0	0	1.26	2.81	0.39	7.56	87.11	0.87
lzt20	0	0.13	2.08	2.02	4.29	67.07	24.29	0.06
lzt21	0.2	0.78	6.07	6.07	5.28	19.77	35.62	22.9	1.96	0.2	0.2
lzt22	0	0.56	2.98	5.59	26.82	62.94	1.12
lzt23	0	0	0	0	0	0.07	1.35	2.63	0.92	70.88	23.15	0.14	0.36	0.5
lzt24	0.44	0.61	4.14	37.41	7.62	12.68	12.72	8.52	6.11	5.19	3.11	0.94	0.31	0.04
lzt25	0.22	0.43	1.52	1.74	2.68	6.44	15.69	27.19	30.22	13.09	0.72
lzt26	0	0	0	1.15	3.15	2.58	77.65	14.61	0.57
lzt27	0.61	0.1	7.55	6.53	1.22	4.39	5	4.08	7.76	44.8	16.43	1.43
lzt28	0.25	0.1	3.71	0.94	0.74	6.77	15.56	10.08	10.97	14.82	18.68	11.41	4.05	1.24	0.1
lzt29	0.3	0.73	1.61	22.37	5.28	6.16	26.34	2.97	0.48	0.85	19.63	12.47	0.73
lzt30	3.7	0.74	47.41	34.07	12.59	0.74

Well there's no easy answer, the character of the files are all very different.

In many cases the A Star parse is reasonably fast (comparable to Chain 3 or something). But in some cases it's quite slow, eg. lzt04, lzt08, lzt28.

Okay, I think that's all the data. We have one point to discuss :

(*) = in all these type of endeavors, we see these anomolies where as we give the optimizer more space to make decisions, it gets better for a while, then starts getting worse. I saw the same thing, but more extreme, with video coding.

Basically what causes this is that you aren't optimizing for your real final goal. If you were optimizing for the total output size, then giving it more freedom should never hurt. But you aren't. With Chain N or with A Star in both cases you are optimizing just some local portion, and it turns out that if you let it make really aggressive decisions trying to optimize the local bit, that can hurt overall.

A similar issue happens with an Huffman optimal parse, becuase you are using the huffman code lengths from the previous parse to do the current parse. That's fine as long as your parse is reasonably similar, but if you let the optimal parser really go nuts, it can start to get pretty far off those statistics, which makes it wrong, so that more optimizing actually gives worse results.

With video coding the main issue I had was that the optimization was generally local (eg. just on one macro block at a time or some such), but it of course affects the future as a source for motion compensation (and in other ways), and it turns out if you do really aggressive optimization on the local decisions, that can wind up hurting overall.

A similar thing can happen in image and video coding if you let optimization proceed very aggressively, because you have to use some simple analytic criterion (such as RMSE - though even if you use a fancier metric the same problems arise). The issue is that the coder can wind up finding strange states that are a good trade-off for RMSE, but wind up looking just horrible visually.

Obviously the correct solution is to optimize with the true final goal in mind. But that's not always possible, either computationally, or because the final goal is subjective.

Generally the solution is to moderate the optimization in some way. You have some heuristic idea of what kind of solutions will provide good globally optimal solutions. (for example, in image/video coding, you might require that the bit rate allocation not create too big of a difference between adjacent blocks). So you sort of want to guide your optimization to start around where you suspect the answer to be, and then you tune it so that you don't allow it to be too aggressive in making whatever decision it thinks is locally optimal.

01-07-12 - Protectionism

2012-01-07T00:00:00.000-08:00

There are some basic economics that I just don't understand, and a lot of the times the accepted "right answer" conflicts with common sense.

One example is it seems to me that buying something locally made is better for the local area than buying something made far away. (for "locality" you may substitute "state" or "nation" or whatever region you want to divide things by).

For me this conjures bad memories of the anti-"Jap" "USA USA" crowd of the '80's that had "buy American" bumper stickers and such ; something in my moral fibers says you should buy the best quality cheapest product. But I don't think that's true.

Consider for the moment the case that there are two products, identical in price and quality. One is locally made, one is foreign made. I contend it is better for the local area (and usually better for you personally) to buy the locally made product. When you do that, the money goes to someone who lives nearby, who spends that money again, and that person spends it, again, etc. This makes the local area prosperous.

(in a purely selfish sense, whether or not making the local area prosperous is good for you or not depends on the details of your situation; if you are a merchant or an altruist, it is good for you; but if your business is international and you would prefer local property values to be low, it might be bad for you; we will assume for the moment that you want the local area to benefit).

So there is some value to buying local and keeping money and industry circulating locally.

So, even if the local product is somewhat more expensive, it still might be better overall if you bought that instead of the foreign product. You have to weigh the benefit of both; the region gains some utility from access to cheaper foreign products, but that is traded off against not circulating that money around the local economy. eg. there's some break even point (in terms of overall utility) ; maybe if the local product costs 20% more, that's the actual break even point.

Of course consumers should not have to make that decision themselves, they should just be able to buy the cheapest product. The correct way to fix that is with government - one of the valuable things that government can do is to make apparent price equal to actual price (eg. to make price proportional to utility, or to move long term costs forward, etc.), or to use laws to bias pricing so that logical purchasing decisions lead to the greatest overall utility (eg. putting penalties on products that help you but hurt others).

The obvious way to make the prices match utility here is either with tarrifs on imports, or subsidies for local production. This is called "protectionism" to attack it, but it seems to me it's just a way of getting the benefit of circulating those dollars locally.

I'm a little disturbed by my conclusion because it's awfully close to the anti-globalization crackpots who claim that modern government financial policy benefits "wall street not main street" (and other slogans).

Granted, in reality, it's too late to go back to pre-1990's protectionism. The cat is out of the bag. And of course in reality protectionism degrades into political gifts for corrupt corporations. But we can ignore those issues for the theoretical discussion.

Also, if you are an extremely altruistic chap you might question the whole goal of maximizing the benefit to your locality (nation/state/fiefdom/whatever). You might say the goal of policies should be to maximize the good for the world. But for the moment let's ignore that and assume that the government of a nation should act to maximize benefit for that nation.

01-06-12 - Surveying is a Powder Keg

2012-01-06T21:10:00.003-08:00

So I got my property surveyed a while ago, because there were some boundaries I wasn't totally sure about, and wanted to see how much space I had for fences, etc.

I should have realized this but did not - surveying is a powder keg. When the surveyor comes out and puts out his stakes and flags, it's like a siren call for neighborhood crazies to come around and dispute the line.

Basically people are retarded and unreasonable, and before just calmly talking to you, they assume you will ask them to take down their fence which is across the line (or whatever). Depending on where you live, the exact force of crazy takes different forms; out in the country you might get shot at; over in the suburbs you might get served with a notice of adverse posession. All just because you hired a surveyor, before you even consider doing anything about it. The crazies seem to see the surveyor's flag as a declaration of war.

The mistake I made was I got the survey and then I wanted some time to think about how I was going to fence things, I didn't just jam up the fences right away. That gave the crazies time, and this is what they did :

(pink flag stake is official from the surveyor of course, and crazy neighbor has put up his own line two feet into my property from the official mark)

Well done, crazy neighbor.

A bit of forehead vein popping and yelling at them got them to remove the post, but I expect more complications of this issue before it is done.

(BTW yelling at people is never satisfying in real life the way it is in fiction. In fiction there's this myth that people are actually good and reasonable, and were just doing something bad for a moment, and when you yell at them they realize their mistake and reform; like if Gorden Ramsay walked in at the right moment and yelled at Hitler he would be like "oh gosh, you're right, I'm so ashamed, I'll try to do better". Furthermore in fiction, they respond to the yelling either by yelling back, giving a satisfying argument, or by accepting the scolding and apologizing. In real life that never happens, what really happens is they try to change the subject, or turn it around and somehow blame you, or make excuses, or bring up random other points that don't matter to the issue (*), and it just leaves you feeling derailed).

(* = this is maybe the most common and most effective response - the completely random diversion into some other story that just leaves me going "WTF?" and totally takes the wind out of my sails. The other super effective tactic that I've noticed from like car salesman and contractors and such is to just completely stone wall you, like they tack on some $500 extra fee that they specifically agreed they wouldn't do, and you're like "hey WTF is this fee that you said wouldn't be there" and they just act like they did nothing wrong and of course you're going to go along with them, like "yep that's the $500 extra rapeage surcharge, so you can pay now by giving me your bank account and social security number..." , wait, what? I'm in the middle of yelling at you, you can't just act like your way is the only way).

01-06-12 - Nice Wiring Bub

2012-01-06T21:10:00.001-08:00

I took off a horrible track light (blyeck, so tacky, track lights and can lights are the worst), and underneath I found this gem :

at first I thought it was just a big wad of masking tape on the end of the wire (bad enough, not an actual insulator, and a fire hazard), but upon peeling the masking tape I found this :

Oh, of course. You spliced on an extra 1 inch of wire, no wire nut, wrapped in masking tape - and the thing that most boggles my mind is that the wire ends are not even twisted in any kind of sane way, they are just randomly balled up around each other. Not to mention the original wires are plenty long without the splice.

Pretty impressive piece of fail.

BTW one of the hazards of old knob & tube wires is that the insulation is only rated to 60 C, but newer light fixtures are allowed to heat up to 90 C (which new Romex can handle). So you need to be careful when installing new light fixtures, and at the very least don't over-bulb (*). One way to solve this (without a ton of rewiring) is to back up the knob and tube a few feet away, put a junction box there, then run new Romex for the last few feet.

(* = I just love to over-bulb ; I can never get enough light; I used to put 100 W's in everything whenever I moved into an apartment. Here I might be a bit more careful about that, because they do generate a lot more heat (BTW I despise the gross inhumane light of CFL's, but one advantage of them with old wiring is they draw much less power (which keeps the wires cool) and they themselves are cool (which doesn't heat up the light fixture and box)). I'm not a huge fan of dimmers (fucking 75 W is already dark enough, I don't need any less than that), but if I could install an *amplifier* that let me over-drive the bulbs that would be sweet (but not in my house, which is apparently wired by paper clips and masking tape)).

It's kind of scary what kinds of disasters can be hiding inside your walls that you don't know about upon purchase (or maybe ever, until they cause water damage or a fire or whatever). I really like doing home improvement work in the garage and the basement, because the walls are unfinished so I can see where the studs are, which is so handy, I can see all the wire runs and junction boxes. It's totally superior.

Covering up your walls is super over-rated. I think if I was designing a modern house it would be all Pompidou Center style with color-coded pipes running around where I could directly access the electricity, water, etc.

If you want a more old fashioned home look, you could still do all your major wire runs around the ceiling and then cover them with a removeable wood crown molding piece. That way if you want to get into the wires, you just pop off the crown molding and you have a wooden box for access.

01-04-12 - Two laws you should hate

2012-01-04T00:00:00.002-08:00

NDAA : makes legal the GWB/Obama policy of indefinite detainment (outside of war zone, Geneva convention, or any legal jurisdiction), and unilateral assasination orders -

� Obama�s Signing Statement on NDAA I have the power to detain Americans� but I won�t Alex Jones' Infowars There's a war on
The NDAA's historic assault on American liberty Jonathan Turley Comment is free guardian.co.uk
The Hit List The Public Applauds As President Obama Kills Two Citizens As A Presidential Prerogative � JONATHAN TURLEY
Senate Votes Overwhelmingly To Allow Indefinite Detention of Citizens � JONATHAN TURLEY

SOPA : basically makes free speech on the internet impossible, by making site hosts legally liable for any content posted on them. Basically allowed private companies to censor the internet at will.

Stop Online Piracy Act - Wikipedia, the free encyclopedia
SOPA for Dummies - Google Docs
House takes Senate's bad Internet censorship bill, tries making it worse

SOPA might not pass in it's worst form, but some lobbyists are pushing very hard for something like this, so the internet is going to get censored unless we fight it very hard.

01-04-12 - Police Brutality

2012-01-04T00:00:00.001-08:00

Much has been made of the outrageous treatment of Occupy protestors by police. But I believe it's been small potatos compared to the rampant, systemic brutality which pervades our nation's police departments. It's fallen out of the news because we're bored of it (we've seen black guys getting beaten by cops a million times) and because it doesn't affect the wealthy, but it has really not gotten better (or not enough, anyway).

Police in American are de-facto above the law. They violate human rights at will, with rarely a punishment greater than suspension or transfer.

Here in Seattle things have gotten shockingly bad, so bad in fact that even the DOJ has made an official report about how bad our police department is. (original here) . What is Seattle's official response? Not to do anything about it, it's to question the methodology of the report. Shameful.

To Protect & Skull-Fuck - Page 1 - News - Seattle - Seattle Weekly
SPDecay - Page 1 - News - Seattle - Seattle Weekly
Seattle sues attorney over public records request Local & Regional Seattle News, Weather, Sports, Breaking News KOMO News
Seattle Police Department Sued by KOMO News for Not Releasing Dash-Cam Videos - Seattle News - The Daily Weekly
Seattle Police A Department in Denial - Page 1 - News - Seattle - Seattle Weekly

One of the few ways that people are getting any justice these days is by getting the dash cam footage to prove that the cops' lies are in fact lies. (see for example Ian Birk lying about John T. Williams "lunging" at him (eerily similar to the very tragic case of Otto Zehm in Spokane in which officers also lied and claimed he "lunged" (with a soda pop bottle, which led them to kill him))). The result of course is that SPD is doing what it can to stop the dash cam system. They are now suing to stop releases of footage under public records disclosures, and have "accidentally" deleted many thousands of hours of footage.

Police Chief Diaz needs to be fired.

But in the larger picture, the big problem is the stone wall and loyalty attitude of police departments; that when there is a case where a police office may have killed a civilian without cause, their attitude is not to investigate and apologize, it's to cover it, draw ranks, support the officer, etc. This attitude makes not just the few bad cops responsible, but every cop who treats his compatriots as beyond reproach or above the law. Loyalty to evil is not admirable. (ask Joe Paterno).

Following a rash of unjustified killings in the 80's, many laws were passed that make it somewhat more difficult for police officers to use their guns. But the gap has been filled by stompings, clubbings, and taserings.

spokane police abuses summary

previous post at cbloomrants

Of course part of the problem is that there is a decent portion of the population that thinks "tough policing" is a good thing.

01-04-12 - Double Pane Glass is a scam

2012-01-04T00:00:00.000-08:00

"Replacement Windows" are shit sold by the window industry to sucker homeowners. The tiny gap (typically less than 1 inch) in a standard double pane IGU (integrate glass unit) is no better (and sometimes worse) than a traditional window + storm.

Throwing out perfectly good lovely old windows for "environmental" reasons is of course retarded; if you want more air proofing and don't already have storm windows, just get some good storms and you're done.

Replacement windows almost always uglier than good old wood windows, which architecturally fit the house and have nice wavy old glass.

Furthermore, they cannot be maintained and repaired in the same way as an old window + storm. When an IGU fails (which they do in 10-20 years typically) it cannot be repaired, it has to be replaced. Old wood windows can be easily taken a part, cleaned, resealed, and can last 100 years. (Vinyl windows and caulk and foam seal strips and so on are similarly problematic - they seem great at first, but they all decay badly in sun and weather, so have to be replaced regularly and can't really be maintained).

Replacement windows are usually shoved inside the existing window framing, and add their own thin frame which makes the opening smaller and adds an extra ugly architectural detail.

It's a standard "sustainable" bullshit corporate ripoff. To sell you some new crap and get you to throw away your perfectly good old windows. (it's like the wonderful irony of "sustainable christmas trees").

This guy addresses the issue in much more detail.

12-20-11 - Grocery Store Lines

2011-12-20T00:00:00.000-08:00

Grocery store lines are a microcosm for how fucking shitty almost every human is, in almost every way.

First of all, you have the fact that nobody shows any basic human courtesy to each other. I almost never see someone with a ton of items let ahead the person with one item. But of course when I let the person with one item go ahead of me, they invariably do something fucked up like ask for a pack of cigarettes (which always takes forever in US grocery stores) or pay with food stamps or some shit. (aside : why is it always such a clusterfuck to pay with food stamps in some groceries? they must have done it a million times, but the checker always acts like someone handed them monopoly money, and the manager has to get called, and forms are filled out, wtf). Of course the people who are paying with coupons and civil war scrip never warn the person lining up behind them that maybe they should pick a different line.

But when the lines get long you really start to see people's souls.

There's the people who stand around and chat right in the middle of the lines. I watch people over and over asking "are you in line? oh, no? okay". Hmm, maybe you should get the fuck out of the line area to have your chit chat!

Then there's the people who can't seem to run a line in a reasonable direction and wind up blocking all the aisles or running it into another line. Invariably it takes a manager to come over and tell people to "please line up over here" since god knows they aren't going to sort themselves out.

Then you get the people who start stamping around and huffing and quickly looking from one side to another like this is the greatest injustice since slavery. You can just see wheels spinning in their heads about how "ridiculous this is" and so on.

There are the people who think that being really pushy in the back of the line is going to speed things up. We're eight people away from the register and they keep jamming their cart into my feet because the person three ahead of us moved. I get out of line to grab a magazine (leaving my cart) and they push into the gap where my body was. Whoah, slow down dick-face, we're still twenty feet from the register, you can chill a little now.

On the flip side then is the people who are absurdly slow about getting their checkout done with. (and of course to double-down on dickishness, it's often the same people who were impatient and pushy when they were way back in line (*)).

There are two general classes of people who fail to check out quickly :

1. The epically incompetent. These people pay with a check, either because they are ancient geezers (excusable) or because they think cards are somehow inferior or checks are more convenient (inexecusable). They might go digging around in their purse for half an hour trying to find exact change, or somehow still don't know they can scan their card before the checker is done.

2. The intentionally slow. These people think everyone needs to chill and slow down; what's the rush? They might chat with the checker a bit. They think everyone else is rotten for being in such a hurry. OMG you epic douchebag; it's fine if you want to live a slow, relaxed, life, but it's not okay to impose that on everyone behind you in line. You probably drive slowly too and think that everyone behind you is in the wrong for wanting to go faster. You probably have a "keep your laws off my body" bumper sticker, and fail to see that your own behavior is the same kind of selfish forcing of your values on others.

(* = the double-dick seems to be the norm for airplane passengers; who are inevitably and annoying and pushy and do a lot of huffing when you are way back in line, but when they actually get up to the TSA guy they still have their shoes on, don't have their id in hand, are drinking a bunch of liquid, and act like it's some big surprise. Same thing with the overhead bin stowage of course).

12-19-11 - SRAM

2011-12-19T00:00:00.000-08:00

SRAM is rolling out a big promotional campaign this year, trying to convince people that their components are actually superior.

They've signed up lots of the pro teams. Just as with car racing, do not be mislead by what the pros use. I see lots of morons on forums saying "well the race team uses this, it must be great". No, the reason the race team uses it is because they are paid to use it.

SRAM double-tap shifters are fucking *awful*. Absolutely retarded. Imagine your right mouse button was taken away and instead you had to double-tap the left to accomplish that function. Yep, it's horrible.

Double-press GUI is always horrible and always should only be used as a last resort. We use it sometimes in games because there just aren't enough buttons on console controllers, but a smart game designer knows that only the secondary functions should go on double-tap buttons (the same goes for "hold" buttons) and the twitch functions should be on their own dedicated button.

Actually it's even worse than that. They don't do the right thing when you're at the edge of the gear shift limits. So like if you are at the low end, you can't go any lower (which you would accomplish by double-tapping), it will still let you single tap (to up-shift). So you're riding up a steep hill and you want a lower gear, you go to double-tap, and oh fuck half way through it the lever won't let you do the double-tap, but you've already single-tapped. There's no way to back out of it, when you let go it will up-shift you and you'll be fucked.

The STI system is just one million billion times better. But it's patented. That's why all these shift levers are so dang expensive, because they're patented.

It's also why there has to be a new lever system every year, a new size of bottom bracket, a new headset system - it's so that the manufacturer can patent it and/or make an exclusive line so that they can rip you off. The old system was perfectly fine functionally, the problem with it was that generic brands were starting to come out with cheap decent components for that system. We can't have that.

It's just like medicine of course, though with medicine it's much more diabolical.

Certainly with medicine it's obvious that there should be laws that prevent the pointless pushing of the new expensive product when it's not actually any better than cheap old solutions.

But I think it would actually be in the world's best interest to have a similar law for everything. It would be hard to phrase and hard to enforce, but the idea is something like - you must make components that are compatible with others on the market unless the incompatibility is for a necessary functional reason. It's actually much better for the free market and competition of products can plug and play and the consumer can choose based on pice and functionality, not compatibilty with some bullshit proprietary interface.

One that annoys me is car parts; most of the car parts for a Porsche or BMW or whatever are actually identical to the ones for a cheaper car (like a VW for example) - but they intentionally make the interface ever so slightly different so that you can't just go buy the cheaper part. The parts are all made by Bosch or whoever major part supplier anyway, it's not like you get a better brand of part for the money. The interesting thing to me is that the car maker doesn't really benefit from this, it's the part maker who does, so there must be some kind of collusion where the car maker gets a kickback in exchange for using the proprietary part.

Maybe the most obvious example is car wheels. Wheels are wheels, there's no need for them to be car specific, but the auto manufacturers intentionally use different bolt spacings (5x130, 4x110, etc) so that you can't go buy cheap mass market wheels for your fancy car. You can cross-shop the exact same wheel with different bolt spacings, and the price difference can be 2X or more.

12-17-11 - LZ Optimal Parse with A Star Part 4

2011-12-17T17:00:00.000-08:00

Continuing ...
Part 1
Part 2
Part 3

So we have our A star parse from last time.

First of all, when we "early out" we still actually fill out that hash_node. That is, you pop a certain "arrival", then you evaluate the early out conditions and decide this arrival is not worth pursuing. You need to make a hash_node and mark it as a dead end, so that when you pop earlier arrivals that see this node, they won't try to visit it again.

One option would be to use a separate hash of just bools that mark dead ends. This could be a super-efficient smaller hash table of bit flags or bloom filters or something, which would save memory and perhaps speed.

I didn't do this because you can get some win from considering parses that have been "early outed". What you do is when you decide to "early out" an arrival, you will not walk to any future nodes that are not yet done, but you *will* consider paths that go to nodes that were already there. In pseudo-code :


pop an arrival

check arrival early outs and just set a flag

for all coding choices at current pos
{
  find next_node
  if next_node exists
    compute cost to end
  else
    if ! early out flag
       push next_node on arrivals stack
}

So the early out stops you from creating any new nodes in the graph walk that you wouldn't have visited anyway, but you can still find new connections through that graph. What this lets you do in practice is drive the early out thresholds tighter.

The other subtlety is that it helps a lot to actually have two (or more) stages of early out. Rather than just stop consider all exit coding choices once you don't like your arrival, you have a couple of levels. If your arrival looks sort of bad but not terrible, then you still consider some of the coding choices. Instead of considering 8 or 16 coding choices, you reduce it to 2 or 4 which you believe are likely advantageous.

The exact details depend on the structure of your back end coder, but some examples of "likely advantangeous" coding choices that you would consider in the intermediate early out case : if you have a "repeat recent offset" structure like LZX/LZMA, then those are obvious things to include in the "likely advantageous". Another one might be RLE or continue-previous type of match codes. Another would be if the literal codes below a certain number of bits with the current statistics. Also the longest match if it's longer than a certain amount.

Okay, so our A star is working now, but we have a problem. We're still just not getting enough early outs, and if you ran this on a big file it will take forever (sometimes).

The solution is to use another aspect we expect from our LZ back end, which is "semi-locality". Locality means that a decision we make now will not have a huge effect way in the future. Yes, it has some effect, because it may change the state and that affects the future, but over time the state changes so many times and adapts to future coding that the decision 4000 bytes ago doesn't matter all that much.

Another key point is that the bad (slow) case occurs when there are lots of parses that cost approximately the same. Because of our early out structure, if there is a really good cheap parse we will generally converge towards it, and then the other choices will be more expensive and they will early out and we won't consider too many paths. We only get into bad degeneracy if there are lots of parses with similar cost. And the thing is, in that case we really don't care which one we pick. So when we find an area of the file that has a huge branching factor that's hard to make a decision about, we are imperfect but it doesn't cost us much overall.

The result is that we can cut up the file to make the parse space tractable. What I do is work in "quanta". You take the current chunk of the file as your quantum and parse it as if it was its own little file. The parse at the beginning of the quantum will be mostly unaffected by the quantum cut, but the parse at the end will be highly affected by the false EOF, so you just throw it out. That is, advance through the first 50% or 75% of the parse, and then start the next quantum there.

There is one special case for the quantum cutting which is long matches that extend past the end of the quantum. What you would see is when outputting the first 50% of the parse, the last code will be a match that goes to the end of the quantum. Instead I just output the full length of the match. This is not ideal but the loss is negligible.

For speed you can go even further and use adaptive quantum lens. On highly degenerate parts of the file, there may be a huge node space to parse that doesn't get early-out'ed. When you detect one of these, you can just reduce the quantum len for that part of the file. eg. you start with a quantum length of 4096 ; if as you are parsing that quantum you find that the hash table occupancy is beyond some threshold (like 1 million nodes for example), you decide the branching factor is to great and reduce the quantum length to 2048 and resume parsing on just the beginning of that chunk. You might hit 1 million nodes again, then you reduce to 1024, etc.

That's it! Probably a followup post with some results numbers and maybe some more notes about subtle issues. I could also do several long posts about ideas I tried that didn't work which I think are sort of interesting.

12-17-11 - LZ Optimal Parse with A Star Part 3

2011-12-17T14:21:00.001-08:00

Continuing ...
Part 1
Part 2

At the end of Part 2 we looked at how to do a forward LZSS optimal parse. Now we're going to add adaptive "state" to the mix.

Each node in the walk of parses represents a certain {Pos,State} pair. There are now too many possible nodes to store them all, so we can't just use an array to store all {Pos,State} nodes we have visited. So hopefully we will not visit them all, so we will store them in a hash table.

We are parsing forward, so for any node we visit (a {Pos,State} will be called a "node") we know how we got there. There can be many ways of reaching the same node, but we only care about the cheapest one. So we only need to store one entering link into each node, and the total cost from the beginning of the path to get to that node.

If you think about the flow of how the forward LZSS parse completes, it's sort of like an ice tendril reaching out which then suddenly crystalizes. You start at the beginning and you are always pushing the longest length choice first - that is, you are taking big steps into the parse towards the end without filling in all the gaps. Once you get to the end with that first long path (which is actually the greedy parse - the parse made by taking the longest match available at each step), then it starts popping backwards and filling in all the gaps. It then does all the dense work, filling backwards towards the beginning.

So it's like the parse goes in two directions - reaching from the beginning to get to the end (with node that don't have enough information), and then densely bubbling back from the end (and making final decisions). (if I was less lazy I would make a video of this).

Anyhoo, we'll make that structure more explicit. The hash table, for each node, stores the cost to get to the end from that node, and the coding choice that gives that cost.

The forward parse uses entry links, which I will henceforth call "arrivals". This is a destination node (a {pos,state}), and the cost from the beginning. (you don't need to store how you got here from the beginning since that can be reproduced at the end by rewalking from the beginning).


Full cost of parse through this node =

arrival.cost_from_head + hash_node.cost_to_tail

Once a node has a cost in the hash table, it is done, because it had all the information it needed at that node. But more arrivals can come in later as we fill in the gaps, so the full cost from the beginning of the parse to the end of the parse is not known.

Okay, so let's start looking at the parse, based on our simple LZSS pseudo-code from last time :


hash table of node-to-end costs starts empty
stack of arrivals from head starts empty

Push {Pos 1,state initial} on stack of arrivals

While stack is not empty :

pop stack; gives you an arrival to node {P,state}

see if node {P,state} is already in the hash
if so
{
  total cost is arrival.cost_from_head + hash_node.cost_to_tail
  done with this arrival
  continue (back to stack popping);
}

For each coding choice {C} at the current pos
{
  find next_state = state transition from cur state after coding choice C
  next_pos = P + C.len
  next_node = {next_pos,next_state]

  if next_node is in the hash table :
  {
    compute cost to end from code cost of {C} plus next_node.cost_to_tail
  }
  else
  {
    push next_node to the arrivals stack (*1)
  }
}

if no pushes were done
{
  then processing of current node is done
  choose the best cost to end from the choices above
  create a node {P,state} in the hash with that cost
}

(*1 = if any pushes are done, then the current node is also repushed first (before other pushes). The pushes should be done in order from lowest pos to highest pos, just as with LZSS, so that the deep walk is done first).

So, we have a parse, but it's walking every node, which is way too many. Currently this is a full graph walk. What we need are some early outs to avoid walking the whole thing.

The key is to use our intuition about LZ parsing a bit. Because we step deep first, we quickly get one parse for the whole segment (the greedy parse). Then we start stepping back and considering variations on that parse.

The parse doesn't collapse the way it did with LZSS because of the presence of state. That is, say I parsed to the end and now I'm bubbling back and I get back to some pos P. I already walked the long length, so I'm going to consider a shorter one. When I walk to the shorter one with LZSS, then states I need would already be done. But now, the nodes aren't done, but importantly the positions have been visited. That is -


At pos P, state S
many future node positions are already done
 (I already walked the longest match length forward)

eg. maybe {P+3, S1} and {P+5, S2} and {P+7, S3} have been done

I a shorter length now; eg. to {P+2,S4}

from there I consider {P+5, S5}

the node is not done, but a different state at P+5 was done.

If the state didn't matter, we would be able to reuse that node and collapse back to O(N) like LZSS.

Now of course state does matter, but crucially it doesn't matter *that much*. In particular, there is sort of a limit on how much it can help.

Consider for example if "state" is some semi-adaptive statistics. Those statistics are adaptive, so if you go far enough into the future, the state will adapt to the coding parse, and the initial state won't have helped that much. So maybe the initial state helps a lot for the next 8 coding steps. And maybe it helps at most 4 bits each time. Then having a better initial state can help at most 32 bits.

When you see that some other parse has been through this same position P, albeit with different state at this position, if that parse has completed and has a total cost, then we know it is the optimal cost through that node, not just the greedy parse or whatever. That is, whenever a hash node has a cost_to_tail, it is the optimal parse cost to tail. If there is a good parse later on in the file, the optimal parse is going to find that parse, even if it starts from a non-ideal state.

This is the form of our early outs :


When you pop an arrival to node {P,S} , look at the best cost to arrive to pos P for any state, 

if arrival.cost_from_head - best_cost_from_head[P] > threshold
  -> early out

if arrival.cost_from_head + best_cost_to_tail[P] > best_cost_total + threshold
  -> early out

where we've introduced two arrays that track the best seen cost to head & tail at each pos, regardless of state. We also keep a best total cost, which is initially set to infinity until we get through a total parse, and then is updated any time we see a new whole-walk cost.

This is just A star. From each node we are trying to find a lower bound for the cost to get to the end. What we use is previous encodings from that position to the end, and we assume that starting from a different state can't help more than some amount.

Next time, some subtleties.

12-17-11 - LZ Optimal Parse with A Star Part 2

2011-12-17T12:52:00.001-08:00

Okay, optimal parsing with A star. (BTW "optimal" parsing here is really a misnomer that goes back to the LZSS backwards parse where it really was optimal; with a non-trivial coder you can't really do an optimal parse, we really mean "more optimal" (than greedy/lazy type parses)).

Part 1 was just a warmup, but may get you in the mood.

The reason for using A Star is to handle LZ parsing when you have adaptive state. The state changes as you step through the parse forward, so it's hard to deal with this in an LZSS style backwards parse. See some previous notes on backwards parsing and LZ here : 1 , 2 , 3

So, the "state" of the coder is something like maybe an adaptive statistical mode, maybe the LZMA "markov chain" state machine variable, maybe an LZX style recent offset cache (also used in LZMA). I will assume that the state can be packed into a not too huge size, maybe 32 bytes or so, but that the count of states is too large to just try them all (eg. more than 256 states). (*1)

(*1 - in the case that you can collapse the entire state of the coder into a reasonably small number of states (256 or so) then different approaches can be used; perhaps more on this some day; but basically any adaptive statistical state or recent offset makes the state space too large for this).

Trying all parses is impossible even for the tiniest of files. At each position you have something like 1-16 options. (actually sometimes more than 16, but you can limit the choices without much penalty (*2)). You always have the choice of a literal, when you have a match there are typically several offsets, and several lengths per offset to consider. If the state of the coder is changed by the parse choice, then you have to consider different offsets even if they code to the same number of bits in the current decision, because they affect the state in the future.

(*2 - the details of this depend on the back end of coder; for example if your offset coder is very simple, something like just Golomb type (NOSB) coding, then you know that only the shortest offset for a given length needs to be considered, another simplification used in LZMA, only the longest length for a given offset is considered; in some coders it helps to consider shorter length choices as well; in general for a match of Length L you need to consider all lengths in [2,L] but in practice you can reduce that large set by picking a few "inflection points" (perhaps more on this some day)).

Okay, a few more generalities. Let's revisit the LZSS backwards optimal parser. It came from a forward style parser, which we can implement with "dynamic programming" ; like this :


At pos P , consider the set of possible coding choices {C}

For each choice (ci), find the cost of the choice, plus the cost after that choice :
{

  Cost to end [ci] = Current cost of choice C [ci] + Best cost to end [ P + C[ci].len ]

}

choose ci as best Cost to end
Best code to end[ P ] = Cost to end [ best ci ]

You may note that if you do this walking forward, then the "Best cost to end" at the next position may not be computed yet. If so, then you suspend the current computation and step ahead to do that, then eventually come back and finish the current decision.

Of course with LZSS the simpler way to do it is just to parse backwards from the end, because that ensures the future costs are already done when you need them. But let's stick with the forward parse because we need to introduce adaptive state.

The forward parse LZSS (with no state) is still O(N) just like the backward parse (this time cost assumes the string matching is free or previously done, and that you consider a fixed number of match choices, not proportional to the number of matches or length of matches, which would ruin the O(N) property) - it just requires more book keeping.

In full detail a forward LZSS looks like this :


Set "best cost to end" for all positions to "uncomputed"

Push Pos 1 on stack of needed positions.

While stack is not empty :

pop stack; gives you a pos P

If any of the positions that I need ( P + C.len ) are not done :
{
  push self (P) back on stack
  push all positions ( P + C.len ) on stack
    in order from lowest to highest pos
}
else
{
  make a choice as above and fill "best cost to end" at pos P
}

If you could not make a choice the first time you visit pos P, then because of the order that we push things on the stack, when you come back and pop P the second time it's gauranteed that everything needed is done. Therefore each position is visited at most twice. Therefore it's still O(N).

We push from lowest to highest len, so that the pops are highest pos first. This makes us do later positions first; that way earlier positions are more likely to have everything they need already done.

Of course with LZSS this is silly, you should just go backwards, but we'll use it to inspire the next step.

To be continued...

12-12-11 - Things I want and cannot find

2011-12-12T00:00:00.001-08:00

1. A true "sauna" near Seattle. A hot room right next to a lake, so I can steam it up and then go jump in the cold lake. We're in the perfect place for it, we have lots of nice cold swimmable lakes, and there are tons of Swedes around here, and yet I can't find one.

There are plenty of "saunas" at spas and health clubs, but without the lake swim it's fucking bullshit. I imagine some rich guy has one at his lakefront home, but I can't get the hookup.

2. A secluded cabin rental. I like the idea of going out in the woods and writing code alone. I can wear some flannel and chop wood for the fire like a real Northwesterner. But all the cabin rentals I can find are in sort of "cabin communities" or near a highway, or some shit. I want a place where you can look out of the big picture window and just see scenery for miles.

3. A good river swim. I found a bunch in CA but I can't find any up here. An ideal river swim has a nice deep "hole" due to rocks or waterfall or something. It should be a 4-5 mile hike from the closest parking to cut down on traffic (or be up a rough road or something, not just right off a highway). Ideally it should not be straight out of snow melt so that it's not ball-breaking freezing cold even in the middle of summer.

4. A nice place to ride. A country lane, no cars, good pavement. God damn I miss this.

12-12-11 - Sense

2011-12-12T00:00:00.000-08:00

One of the most important skills in an employee is the sense to know when to ask for help and when not to. To know when they should just make a decision on their own vs. ask to make sure their choice is okay. To know when they need to call a meeting about something vs. when not to disturb others about it.

It's incredibly rare actually to find someone who has the sense to get this just right. I think it's very undervalued.

When you're a manager, the most awesome thing you can have is an employee you can trust. That means no unpleasant surprises. If you give them a task, it will be done on time, or you will be notified with enough notice to take action. You won't find out that they're slipping when it's too late to do anything about it. You won't have them claim to be done and then upon inspection find out that they've done it all wrong. You can just assign the task off and then you don't have to worry about it any more. You don't have to follow up and keep pinging them for status updates.

Someone with a great deal of sense will just know to give you status updates at the appropriate intervals. Not too often that they waste your time, but not too infrequently - they should always come in just before you start wondering "WTF happened to this task?".

One of the most crucial things is knowing what decisions they need to get approval for. It sucks to have an employee who asks about every little thing. "should I put this button here or here? should I make another file for this code or put it in this file?" Just make a fucking decision yourself, I don't care! But it also sucks to have someone go off and do all kinds of crazy shit without asking, like "oh yeah I ripped out the old animation system and am doing a new one" ; uh, you did what? and you didn't ask me first? WTF. Both are very common.

Of course the definition of the "right amount of approval" depends on the manager, and a key part of having good "sense" is actually social adaptation - it's about adapting to your situation and learning what is wanted of you. Many of the type-A left-brain coders never get this; part of your job as an employee is always interacting with other human beings, even if it's only with your boss, and there is no rational absolute answer about the right way to communicate, you have to feel it out and adapt.

Of course part of the role of a good manager is to teach these things, and to help people who may have good skills but not much "sense".

It's actually more annoying in personal life than in business life. For example you're having a dinner party and somebody volunteers to bring the wine, and then they show up with none, or they show up with a box of ripple. WTF dude, I could have just gotten it myself, if you're going to drop the ball, you need to notify someone with sufficient warning.

The annoying thing about the non-business world is you can't check up on them; like "hey can you give me a status update on that wine purchasing?" because you would be considered a huge dick.

A lot of this goes along with what I call "basic professionalism". Like if I assign you a crucial task that I need done today, don't go home without checking in with me and telling me it's done or not. If you think I assigned you too much and you can't get it done in time, don't go pout, come and tell me about it.

Another aspect of "basic professionalism" is knowing when to shut up. Like if you think the company is going in the wrong direction - raise the issue to your managers, that's good, if you have a good boss they want that feedback. But after they call a meeting and everyone disagrees with you and the decision is made to go on the path you don't like - it's time to shut up about it. We don't want to hear complaints every day.

A related aspect is knowing who it's appropriate to say things to. When we have someone from the publisher touring the studio, that is not the time to point out that you don't like the design of the lead character.

"Basic professionalism" is sort of a level below having good "sense" but it's also actually surprisingly hard to find.

One of the worst situations is to have someone who is not great about "sense" or "basic professionalism" but is touchy about it. Most people are not perfect on these points, and that's okay, but if you're not then you need a certain amount of supervision. That's just the way work gets done, but some people act like it's a personal affront to be monitored.

Like they occasionally drop the ball on tasks, you decide, okay I just have to ask for daily status reports. Then they get all pissy about it, "don't you trust me" or it's "too much beaurocracy" blah blah.

Or if they don't come to you and ask questions at the appropriate time, then you have to pre-screen all their approaches. Like sometimes you assign them a task and they'll just go off and start doing it wrong without saying anything. Now what you have to do is when you assign a task you have to say "can you tell me how you're going to approach this?" to make sure they don't say something nutso.

12-09-11 - Kittens

2011-12-09T00:00:00.000-08:00

We want to get a kitten (since we have a stable house now), and I would like to just get a kitten from a home but WTF they don't exist any more.

When I was a kid, every couple of weeks some family in the neighborhood would have kittens and put out a sign. You could go to their house and see the kittens play and pick one. You could see if they were coming from a good home where they got socialized. You could see how old they were to know they weren't separated from their mom at too young an age.

There just isn't any of this anymore. It seems to have all been corporatized into kitten adoption centers.

Yeah yeah yeah you should adopt an a deformed adult cat that drools and has mange. No thanks. Part of the reason why I can't just find a normal home to adopt from is all the pet-adoption-nazis make it so that you can't use craigslist (or whatever) to find pets.

Also all the adoption agencies have strict spay/neuter at time of adoption rules. When I was a kid when we would get a cat sometimes we would not spay right away so that we could get a batch of kittens and keep one and give the result away. It was delightful to have a line of generations and a bunch of kittens to play with. That tradition seems to be all gone. The result is that the babies only come from strays or weirdos outside the system. It's sort of like if all law abiding citizens were castrated, then the only children in the world would be from criminals.

Boo.

Also, in other cat news, it turns out our professional cat sitter grossly overfed our cat while we were away in Hawaii. This despite verbal and written instructions on the correct amount to feed her. So she's sickly obese on our return.

How fucking hard is it to follow basic instructions? Jesus christ, I'm trying not to be a rich old crank, but I can't help thinking things like "it's so hard to find good help" and that the poor are poor because they're fucking retarded. (*). Half a cup means fucking half a cup, not "oh, I'll feed her until she stops eating like she's starving". You are the fucking help, you don't get to make your own decisions when I gave you specific orders.

What makes it even worse is that she (the cat sitter) gave us the usual condescending "I know so much about cats" bullshit when we interviewed her. Hey lady, I've watched an episode of the Dog Whisperer too, I'm not impressed by your amateur pet psychiatry.

* = you would think that it should be easy to find someone who could like get your groceries for you, or build you a fence, or pay your bills, or whatever, but it's actually really hard. It's amazing how badly the average person will fuck up the most basic assignments. To get someone that is smart enough that you can trust them to do those things, you have to hire someone in the top 1% of intellects, someone who could make $100k a year. It's actually sort of easy to hire someone really smart who costs a lot of money, and it's easy to hire someone who is just manual labor that you have to constantly supervise, but to hire someone in between that you can trust enough not to supervise but doesn't cost a fortune is hard because people are epic fuck ups.

12-08-11 - Some Semaphores

2011-12-08T16:05:00.001-08:00

In case you don't agree with Boost that Semaphore is too "error prone" , or if you don't agree with C++0x that semaphore is unnecessary because it can be implemented from condition_var (do I need to point out why that is ridiculous reasoning for a library writer?) - here are some semaphores for you.

I've posted a fastsemaphore before, but here's a more complete version that can wrap a base semaphore.


template< typename t_base_sem >
class fastsemaphore_t
{
private:
    t_base_sem m_base_sem;
    atomic<int> m_count;

public:
    fastsemaphore_t(int count = 0)
    :   m_count(count)
    {
        RL_ASSERT(count > -1);
    }

    ~fastsemaphore_t()
    {
    }

    void post()
    {
        if (m_count($).fetch_add(1,mo_acq_rel) < 0)
        {
            m_base_sem.post();
        }
    }

    void post(int count)
    {
        int prev = m_count($).fetch_add(count,mo_acq_rel);
        if ( prev < 0)
        {
            int num_waiters = -prev;
            int num_to_wake = MIN(num_waiters,count);
            // use N-wake if available in base sem :
            // m_base_sem.post(num_to_wake);
            for(int i=0;i<num_to_wake;i++)
            {
                m_base_sem.post();
            }
        }
    }
    
    bool try_wait()
    {
        // see if we can dec count before preparing the wait
        int c = m_count($).load(mo_acquire);
        while ( c > 0 )
        {
            if ( m_count($).compare_exchange_weak(c,c-1,mo_acq_rel) )
                return true;
            // c was reloaded
            // backoff here optional
        }
        return false;
    }
        
    void wait_no_spin()
    {
        if (m_count($).fetch_add(-1,mo_acq_rel) < 1)
        {
            m_base_sem.wait();
        }
    }
    
    void wait()
    {
        int spin_count = 1; // ! set this for your system
        while(spin_count--)
        {
            if ( try_wait() ) 
                return;
        }
        
        wait_no_spin();
    }
    
    
    int debug_get_count() { return m_count($).load(); }
};

when m_count is negative it's the number of waiters (plus or minus people who are about to wait, or about to be woken).

Personally I think the base semaphore that fastsem wraps should just be your OS semaphore and don't worry about it. It only gets invoked for thread wake/sleep so who cares.

But you can easily make Semaphore from CondVar and then put fastsemaphore on top of that. (note the semaphore from condvar wake N is not awesome because CV typically doesn't provide wake N, only wake 1 or wake all).

Wrapping fastsem around NT's Keyed Events is particularly trivial because of the semantics of the Keyed Event Release. NtReleaseKeyedEvent waits for someone to wake if there is noone. I've noted in the past that Win32 event is a lot like a semaphore with a max count of 1 ; a problem with building a Semaphrore from normal Event would be that you Set it when it's already Set, you effectively run into the max count and lose your Set, but this is impossible with KeyedEvent. With KeyedEvent you get exactly one wake from Wait for each Release.

So, if we wrap up keyed_event for convenience :


struct keyed_event
{
    HANDLE  m_keyedEvent;

    enum { WAITKEY_SHIFT = 1 };

    keyed_event()
    {
        NtCreateKeyedEvent(&m_keyedEvent,EVENT_ALL_ACCESS,NULL,0);
    }
    ~keyed_event()
    {
        CloseHandle(m_keyedEvent);
    }

    void wait(intptr_t key)
    {
        RL_ASSERT( (key&1) == 0 );
        NtWaitForKeyedEvent(m_keyedEvent,(PVOID)(key),FALSE,NULL);
    }

    void post(intptr_t key)
    {
        RL_ASSERT( (key&1) == 0 );
        NtReleaseKeyedEvent(m_keyedEvent,(PVOID)(key),FALSE,NULL);
    }
};

Then the base sem from KE is trivial :


struct base_semaphore_from_keyed_event
{
    keyed_event ke;

    base_semaphore_from_keyed_event() { }
    ~base_semaphore_from_keyed_event() { }
    
    void post() { ke.release(this); }   
    void wait() { ke.wait(this); }
};

(note this is a silly way to use KE just for testing purposes; in practice it would be shared, not one per sem - that's sort of the whole point of KE).

(note that you don't ever use this base_sem directly, you use it with a fastsemaphore wrapper).

I also revisited the semaphore_from_waitset that I talked about a few posts ago. The best I can come up with is something like this :


class semaphore_from_waitset
{
    waitset_simple m_waitset;
    std::atomic<int> m_count;

public:
    semaphore_from_waitset(int count = 0)
    :   m_count(count), m_waitset()
    {
        RL_ASSERT(count >= 0);
    }

    ~semaphore_from_waitset()
    {
    }

public:
    void post()
    {
        m_count($).fetch_add(1,mo_acq_rel);
        m_waitset.notify_one();
    }

    bool try_wait()
    {
        // see if we can dec count before preparing the wait
        int c = m_count($).load(mo_acquire);
        while ( c > 0 )
        {
            if ( m_count($).compare_exchange_weak(c,c-1,mo_acq_rel) )
                return true;
            // c was reloaded
        }
        return false;
    }

    void wait(wait_thread_context * cntx)
    {
        for(;;)
        {
            // could spin a few times on this :
            if ( try_wait() )
                return;
    
            // no count available, get ready to wait
            waiter w(cntx);
            m_waitset.prepare_wait(&w);
            
            // double check :
            if ( try_wait() )
            {
                // (*1)
                m_waitset.retire_wait(&w);
                // pass on the notify :
                int signalled = w.flag($).load(mo_acquire);
                if ( signalled )
                    m_waitset.notify_one();
                return;
            }
            
            w.wait();
            m_waitset.retire_wait(&w);
            // loop and try again
        }
    }
    
    void wait()
    {
        wait_thread_context cntx;
        wait(&cntx);
    }
};

The funny bit is at (*1). Recall before we talked about a race that can happen if two threads post and two other threads pop. If one of the poppers gets through to *1 , it dec'ed the sem but is still in the waitset, one pusher might then signal this thread, which is a wasted signal, and the other waiter will not get a signal, and you have a "deadlock" (not a true deadlock, but an unexpected permanent sleep, which I will henceforth call a deadlock).

You can fix that by detecting if you recieved a signal while you were in the waitset. That's what's done here now. While it is not completely ideal from a performance perspective, it's a rare race case, and even when it happens the penalty is small. I still don't recommend using semaphore_from_waitset unless you have a comprehensive waitset-based system.

(note that in practice you would never make a wait_thread_context on the stack as in the example code ; if you have a waitset-based system it would be in the TLS)

Another note :

I have mentioned before the idea of "direct handoff" semaphores. That is, making it such that thread wakeup implies you get to dec count. For example "base_semaphore_from_keyed_event" above is a direct-handoff semaphore. This is as opposed to "optimistic" semaphores, in which the wakeup just means "you *might* get to dec count" and then you have to try_wait again when you wake up.

Direct handoff is neat because it gaurantees a minimum number of thread wakeups - you never wake up a thread which then fails to dec count. But they are in fact not awesome. The problem is that you essentially have some of your semaphore count tied up in limbo while the thread wakeup is happening (which is not a trivial amount of time).

The scenario is like this :


1. thread 1 does a sem.wait

2. thread 2 does a sem.post 
  the sem is "direct handoff" the count is given to thread 1
  thread 1 starts to wake up

3. thread 3 (or thread 2) now decides it can do some consuming
  and tries a sem.wait
  there is no sem count so it goes to sleep

4. thread 1 wakes up and processes its received count

You have actually increased latency to process the message posted by the sem, by the time between steps 3 and 4.

Basically by not pre-deciding who will get the sem count, you leave the opportunity for someone else to get it sooner, and sooner is better.

Finally let's have a gander at the Linux sem : sem_post and sem_wait

If we strip away some of the gunk, it's just :


sem_post()
{

    atomic_add( & sem->value , 1);

    atomic_full_barrier (); // (*1)

    int w = sem->nwaiters; // (*2)

    if ( w > 0 )
    {
        futex_wake( & sem->value, 1 );  // wake 1
    }

}

sem_wait()
{
    if ( try_wait() ) return;

    atomic_add( & sem->waiters , 1);

    for(;;)
    {
        if ( try_wait() ) break;

        futex_wait( & sem->value, 0 ); // wait if sem value == 0
    }

    atomic_add( & sem->waiters , -1);
}

Some quick notes : I believe the barrier at (*1) is unnecessary ; they should be doing an acq_rel inc on sem->value instead. However, as noted in the previous post about "producer-consumer" failures, if your producer is not strongly synchronized it's possible that this barrier helps hide/prevent bugs. Also at (*2) in the code they load nwaiters with plain C which is very sloppy; you should always load lock-free shared variables with an explicit load() call that specifies memory ordering. I believe the ordering constraint there is the load of nwaiters needs to stay after the store to value; the easiest way is to make the inc on value be an RMW acq_rel.

The similarity with waitset should be obvious, but I'll make it super-clear :


sem_post()
{

    atomic_add( & sem->value , 1);
    atomic_full_barrier ();

    // waitset.notify_one :
    {
        int w = sem->nwaiters;
        if ( w > 0 )
        {
            futex_wake( & sem->value, 1 );  // wake 1
        }
    }
}

sem_wait()
{
    if ( try_wait() ) return;

    // waitset.prepare_wait :
    atomic_add( & sem->waiters , 1);

    for(;;)
    {
        // standard double-check :
        if ( try_wait() ) break;

        // waitset.wait()
        // (*3)
        futex_wait( & sem->value, 0 ); // wait if sem value == 0
    }

    // waitset.retire_wait :
    atomic_add( & sem->waiters , -1);
}

It's exactly the same, but with one key difference at *3 - the wait does not happen if count is not zero, which means we can not receive the wait wakeup from futex_wake if we don't need it. This removes the need for the re-pass that we had in the waitset semaphore.

This futex semaphore is fine, but you could reduce the number of atomic ops by storing count & waiters in one word.

12-05-11 - Surprising Producer-Consumer Failures

2011-12-05T18:11:00.000-08:00

I run into these a lot, so let's have a quick glance at why they happen.

You're trying to do something like :


Thread1 :

Produce 1
sem.post

Thread2 :

Produce 2
sem.post

Thread 3 :

sem.wait
Consume 1

Thread 4 :

sem.wait
Consume 2

and we assert that the Consume succeeds in both cases. Produce/Consume use a queue or some other kind of lock-free communication structure.

Why can this fail ?

1. A too-weak semaphore . Assuming out Produce and Consume are lock-free and not necessarily synchronized on a single variable with something strong like an acq_rel RMW op, we are relying on the semaphore to synchronize publication.

That is, in this model we assume that the semaphore has something like an "m_count" internal variable, and that both post and wait do an acq_rel RMW on that single variable. You could certainly make a correct counting semaphore which does not have this behavior - it would be correct in the sense of controlling thread flow, but it would not provide the additional behavior of providing a memory ordering sync point.

You usually have something like :


Produce :
store X = A
sem.post // sync point B

Consume:
sem.wait // sync point B
load X  // <- expect to see A

you expect the consume to get what was made in the produce, but that is only gauranteed if the sem post/wait acts as a memory sync point.

There are two reasons I say sem should act like it has an internal "m_count" which is acq_rel , not just release at post and acquire at wait as you might think. One is you want sem.wait to act like a #StoreLoad, so that the loads which occur after it in the Consume will see preceding stores in the Produce. An RMW acq_rel is one way to get a #StoreLoad. The other is that by using an RMW acq_rel on a single variable (or behaving as if you do), it creates a total order on modifications to that variable. For example if T3 seems T1.post and T2.post and then does its T3.wait , T4 cannot see T1.post T3.wait T4.wait or any funny other order.

Obviously if you're using an OS semaphore you aren't worrying about this, but there are lots of cases where you use this pattern with something "semaphore-like" , such as maybe "eventcount".

2. You're on POSIX and forget that sem.wait has spurious wakeups on POSIX. Oops.

3. Your queue can temporarily appear smaller than it really is.

Say, as a toy example, adding a node is done something like this :


new_node->next = NULL;

old_head = queue->head($).exchange( new_node );
// (*)
new_node->next = old_head;

There is a moment at (*) where you have truncated the queue down to 1 element. Until you fix the next pointer, the queue has been made to appear smaller than it should be. So pop might not get the items it expects to get.

This looks like a bad way to do a queue, but actually lots of lock free queues have this property in more or less obvious ways. Either the Push or the Pop can temporarily make the queue appear to be smaller than it really is. (for example a common pattern is to have a dummy node, and if Pop takes off the dummy node, it pushes it back on and tries again, but this causes the queue to appear one item smaller than it really is for a while).

If you loop, you should find the item that you expected in the queue. However, this is a nasty form of looping because it's not just due to contention on a variable; if in the example above the thread is swapped out while it sits at point (*), then nobody can make progress on this queue until that thread gets time.

The result I find is that ensuring that waking from sem.wait always implies there is an item ready to pop is not worth the trouble. You can do it in isolated cases but you have to be very careful. A much easier solution is to loop on the pop.

12-03-11 - Worker Thread system with reverse dependencies

2011-12-03T10:53:00.001-08:00

In the previous episode we looked at a system for doing work with dependencies.

That system is okay; I believe it works, but it has two disadvantages : 1. It requires some non-standard synchronization primitives such as OR waits, and 2. There is a way that it can fail to do work as soon as possible; that is, there is the possibility for moments when work could be done but the worker that could do it is asleep. It's one of our design goals to not let that happen so let's see why it happens :

The problem basically is the NR (not ready) queue. When we have no RTR (ready to run) work, we popped one item from the NR queue and waited on its dependencies. But there could be other items later in the NR queue which become ready sooner. If the items in the NR queue become ready to run in order, this doesn't occur, but if they can become ready in different orders, we could miss out on chances to do work.

Anyhoo, both of these problems go away and everything becomes much simpler if we reformulate our system in terms of "forward dependencies" instead of "backward dependencies".

Normal "dependencies" are backwards; that is, A depends on B and C, which were created earlier in time. The opposite direction link I will call "permits" (is there a standard term for this?). That is, B and C permit A. A needs 2 permissions before it can run.

I propose that it is conceptually easier to set up work in terms of "dependencies", so the client still formulates work items with dependencies, but when they are submitted to be run, they are converted into "permissions". That is, A --> {B,C} is changed into B --> {A} and C --> {A}.

The main difference is that there is no longer any "not ready" queue at all. NR items are not held in any global list, they are only pointed to by their dependencies. Some dependency back in the tree should be ready to run, and it will then be the root that points through various NR items via permission links.

With no further ado, let's look at the implementation.

The worker thread becomes much simpler :


worker :

wait( RTR_sem );

pop RTR_queue and do work

that's it! Massively simpler. All the work is now in the permissions maintenance, so let's look at that :

How do we maintain permissions? Each item which is NR (not ready) has a (negative) count of the # of permissions needed before it can run. Whenever an item finishes, it walks its permission list and incs the permit count on the target item. When the count reaches zero, all permissions are done and the item can now run.

A work item now has to have a list of permissions. In my old system I had just a fixed size array for dependencies; I found that [3] was always enough; it's simply the nature of work that you rarely need lots of dependencies (and in the very rare cases that you do need more than 3, you can create a dummy item which only marks itself complete when many others are done). But this is not true for permissions, there can be many on one item.

For example, a common case is you do a big IO, and then spawn lots of work on that buffer. You might have 32 work items which depend on the IO. This only needs [1] when expressed as dependencies, but [32] when expressed as permissions. So a fixed size array is out and we will use a linked list.

The maintenance looks like this :


submit item for work :

void submit( work_item * wi , work_item * deps[] , int num_deps )
{

    wi->permits = - num_deps;

    if ( num_deps == 0 )
    {
        RTR_queue.push( p );
        RTR_sem.post();
        return;
    }

    for(int i=0;i<num_deps;i++)
    {
        deps[i]->lock();

        if ( ! deps[i]->is_done )
        {
            deps[i]->permits_list.push( wi );
        }
        else
        {
            int prev = wi->permits.fetch_add(1); // needs to be atomic
            if ( prev == -1 ) // permitted (do this also if num_deps == 0)
            {
                RTR_queue.push( p );
                RTR_sem.post();
            }
        }

        deps[i]->unlock();
    }

}


when an item is completed :

void complete( work_item * wi )
{
    wi->lock();

    set wi->is_done

    swap wi->permits_list to local permits_list

    wi->unlock();

    for each p in permits_list
    {
        int prev = p->permits.fetch_add(1);

        if ( prev == -1 )
        {
            // p is now permitted

            RTR_queue.push( p );
            RTR_sem.post();
        }
    }
}

the result is that when you submit not-ready items, they go into the permits list somewhere, then as their dependencies get done their permits count inc up towards zero, when it hits zero they go into the RTR queue and get picked up by a worker.

The behavior is entirely the same as the previous system except that workers who are asleep because they have no RTR work can wake up when any NR item becomes RTR, not just when the single one they popped becomes RTR.

One annoyance with this scheme is you need to lock the item to maintain the permits_list ; that's not really a big deal (I use an indexed lock system similar to Nt Keyed Events, I don't actually put a lock object on each item), but I think it's possible to maintain that list correctly and simply lock free, so maybe we'll revisit that.

ADDENDUM : hmm , not easy to do lock free. Actually maintaining the list is not hard, and even doing it and avoiding races against the permitted count is not hard, the problem is that the list is in the work item and items can be deleted at any time, so you either need to hold a lock on the item to prevent deletion, or you need something like RCU or SMR.

12-03-11 - RAD - Hawaii Branch

2011-12-03T02:00:00.000-08:00

It's a pretty nice place to work. The ergonomics of the picnic table are not half bad actually. Very glad I brought my keyboard; wish the laptop screen was bigger.

12-02-11 - Natural Expression

2011-12-02T15:14:00.000-08:00

It's so nice when you find the "natural" way to express a coding problem. All of a sudden everything because so much simpler and the answers just start popping out at you. Like oh, and I can do this here, and this automatically happens just the way I wanted. Tons of old code just disappears that was trying to solve the problem in the "un-natural" way.

It doesn't change the code; in the end it all becomes assembly language and it can do the same thing, but changing the way you write it can change the way you think about it. Also when you find an simple elegant way to express things, it sort of makes it feel "right", whereas if you are getting the same thing done through a series of kludges and mess, it feels horrible, even though they are accomplishing the same thing.

It reminds me of physics. I think some of the greatest discoveries the past century in physics were not actually discoveries of any phenomenom, but just ways to write the physics down. In particular I cite Dirac's Bra-Ket notation and Feynman's path integrals.

Neither one added any new physics. If you look at it in a "positivist" view point, they did nothing - the actual observable predictions were the same. The physics all existed in the equations which were already known. But they opened up a new understanding, and just made it so much more natural and easier to work with the equations, and that can actually have huge consequences.

Dirac's bra ket for example made it clear that quantum mechanics was about Hilbert spaces and Operators. Transformation between different basis spaces became a powerful tool, and very useful and elegant things like raising and lowering operators popped out. Quantum mechanics at the time was sort of contraversial (morons like Einstein were still questioning it), and finding a clear elegant solid way to write it down made it seem more reasonable. (physicists have a semi-irrational distrust of any physical laws that are very complicated or vague or difficult to compute with; they also have a superstition that if a physical law can be written in a very concise way, it must be true; eg. when you write Maxwell's equations as d*F = J).

Feynman's path integrals came along just at a time when Quantum Field Theory was in crisis; there were all these infinities which make the theory impossible to calculate with. There were some successful computations, and it just seemed like the right way to extend QM to fields, so people were forging ahead, but these infinities made it an incomplete (and possibly wrong) theory. The path integral didn't solve this, but it made it much easier to see what was actually being computed in the QFT equations - rather than just a big opaque integral that becomes infinity and you don't know why, the path integral lets you separate out the terms and to pretend that they correspond to physical particles flying around in many different ways. It made it more obvious that QFT was correct, and what renormalization was doing, and the fact that renormalization was a physically okay way to fix the infinities.

(while I say this is an irrational superstition, it has been the fact that the laws of physics which are true wind up being expressable in a concise, elegant way (though that way is sometimes not found for a long time after the law's discovery); most programmers have the same supertition, when we see very complex solutions to problems we tend to turn up our noses with distate; we imagine that if we just found the right way to think about the problem, a simple solution would be clear)

(I know this history is somewhat revisionist, but a good story is more important than accuracy, in all things but science)

Anyhoo, it's nice when you get it.

11-30-11 - Basic sketch of Worker Thread system with dependencies

2011-11-30T17:27:00.000-08:00

You have a bunch of worker threads and work items. Work items can be dependent, on other work items, or on external timed events (such as IO).

I've had some trouble with this for a while; I think I finally have a scheme that really works.

There are two queues :


RTR = ready to run : no dependencies, or dependencies are done

NR = not ready ; dependencies still pending

Each queue has an associated semaphore to count the number of items in it.

The basic work popping that each worker does is something like :


// get all available work without considering sleeping -
while( try_wait( RTR_sem ) )
{
    pop RTR_queue and do work
}

// (optionally spin a few times here and check RTR_sem)

// I may have to sleep -

wait( RTR_sem OR NR_sem ); // (*1)

if ( wakeup was from RTR_sem )
{
    pop RTR_queue and do work
}
else
{
    NRI (not ready item) = pop NR_queue
    deps = get dependencies that NRI needs to wait on

    wait( deps OR RTR_sem ); // (*3)

    if ( wakeup was from RTR_sem )
    {
        push NRI back on NR_queue and post NR_sem  // (*4)
        pop RTR_queue and do work
    }
    else
    {
        wakeup was because deps are now done
        NRI should be able to run now, so do it
        (*2)
    }  
}

*1 : the key primitive here is the ability to do a WFMO OR wait, and to know which one of the items signalled you. On Windows this is very easy, it's just WaitForMultipleObjects, which returns the guy who woke you. On other platforms it's trickier and probably involves rolling some of your own mechanisms.

Note that I'm assuming the semaphore Wait() will dec the semaphore at the time you get to run, and the OR wait on multiple semaphores will only dec one of them.

*2 : in practice you may get spurious wakeups or it may be hard to wait on all the dependencies, so you would loop and recheck the deps and possibly wait on them again.

How this differs from my previous system :

My previous system was more of a traditional "work stealing" scheme where each worker had its own queue and would try to just push & pop works from its own queue. This was lower overhead in the fast path (it avoids having a single shared semaphore that they have to contend on, for example), but it had a lot of problems.

Getting workers to go to sleep & wake up correctly in a work stealing scheme is a real mess. It's very hard to tell when you have no work to do, or when you have enough work that you need to wake a new worker, because you don't atomically maintain a work count (eg. a semaphore). You could fix this by making an atomic pair { work items, workers awake } and CAS that pair to maintain it, but that's just a messy way of being a semaphore.

The other problem was what happens when you have dependent work. You want a worker to go to sleep on the dependency, so that it yeilds CPU time, but wakes up when it can run. I had that, but then you have the problem that if somebody else pushes work that can immediately run, you want to interrupt that wait on the dependency and let the worker do the ready work. The semaphore OR wait fixes this nicely.

If you're writing a fractal renderer or some such nonsense then maybe you want to make lots of little work items and have minimal overhead. But that's a very special purpose rare case. Most of the time it's much more important that you do the right work when possible. My guiding principles are :

If there is no work that can be done now, workers should go to sleep (yield CPU)
If there is work that can be done now, workers should wake up
You should not wake up a worker and have it go back to sleep immediately
You should not have work available to do but the workers sleeping

Even in the "fractal renderer" sort of case, where you have tons of non-dependent work items, the only penalty here is one extra semaphore dec per item, and that's just a CAS (or a fetch_add) assuming you use something like "fastsemaphore" to fast-path the case of being not near zero count.

There is one remaining issue, which is when there is no ready-to-run work, and the workers are asleep on the first semaphore (they have no work items). Then you push a work item with dependencies. What will happen in the code sketch above is that the worker will wake up, pop the not ready item, then go back to sleep on the dependency. This violates article 3 of the resolution ("You should not wake up a worker and have it go back to sleep immediately").

Basically from *1 to *3 in the code is a very short path that wakes from one wait and goes into another wait; that's always bad.

But this can be fixed. What you need is "wait morphing". When you push a not-ready work item and you go into the semaphore code that is incrementing the NR_sem , and you see that you will be waking a thread - before you wake it up, you take it out of the NR_sem wait list, and put it into the NRI's dependency wait list. (you leave it waiting on RTR_sem).

That is, you just leave the thread asleep, you don't signal it to wake it up, it stays waiting on the same handle, but you move the handle from NR_sem to the dependency. You can implement this a few ways. I believe it could be done with Linux'es newer versions of futex which provide wait morphing. You would have to build your semaphore and your dependency waiting on futex, which is easy to do, then wait morph to transfer the wait. Alternatively if you build them on "waitset" you simply need to move an item from one waitset to the other. This can be done easily if your waitset uses a mutex to protect its internals, you simply lock both mutexes and move the waitable handle with both held.

The net result with wait morphing is very nice. Say for example are you workers are asleep. You create a work item that is dependent on an IO and push it. None of the workers get woken up, but one of them is changed from waiting on work available to waiting on the dependency. When the IO completes it wakes that worker and he runs. If somebody pushed a ton of work in the mean time, all the workers would be woken and they would do that work, and the dependent work would be pushed back on the NR queue and set aside while they did RTR work.

ADDENDUM : at the spot marked (*4) :


push NRI back on NR_queue and post NR_sem // (*4)
pop RTR_queue and do work

In real code you need do something a bit more complex here. What you do is something like :


if ( NRI is ready ) // double check
{
  RTR_sem.post() // we woke from RTR_sem , put it back
  do NRI work
}
else
{
  push NRI onto NR_lifo and post NR_sem
  pop RTR_queue and do work
}

we've introduced a new queue , the NR_lifo which is a LIFO (eg. stack). Now whenever you get an NR_sem post, you do :


// NR_sem just returned from wait so I know an NR item is available :

NRI = NR_lifo.pop()
if ( NRI == NULL )
  NRI = NR_queue.pop()

the item must be in one or the other and we prefer to take from the LIFO first. Basically the LIFO is a holding area for items that were popped off the FIFO and were not yet ready, so we want to keep trying to run those before we go back to the FIFO. You can use a single semaphore to indicate that there is an item in either queue.

11-30-11 - Some more Waitset notes

2011-11-30T02:00:00.000-08:00

The classic waitset pattern :


check condition

waiter w;
waitset.prepare_wait(&w);

double check condition

w.wait();

waitset.retire_wait(&w);

lends itself very easily to setting a waiter flag. All you do is change the double check into a CAS that sets that flag. For example say your condition is count > 0 , you do :


if ( (count&0x7FFFFFFF) == 0 )
{
    waiter w;
    waitset.prepare_wait(&w);

    // double check condition :
    int c = count.fetch_or( 0x80000000 ); // set waiter flag and double check
    if ( (c&0x7FFFFFFF) == 0 )
        w.wait();

    waitset.retire_wait(&w);
}

then in notify, you can avoid signalling when the waiter flag is not set :


// publish :
int c = count.atomic_inc_and_mask(1,0x7FFFFFFF);
// notify about my publication if there were waiters :
if ( c & 0x80000000 )
  waitset.notify();

(note : don't be misled by using count here; this is still not a good way to build a semaphore; I'm just using an int count as a simple way of modeling a publish/consume.

I was being obtuse before when I wrote about the problems with waitset OR. It is important to be aware of those issues when working with waitsets, because they are inherent to how waitsets work and you will encounter them in some form or other, but of course you can do an OR if you extend the basic waitset a little.

What you do is give waiter an atomic bool to know if it's been signalled, something like :


struct waiter
{
  atomic<bool> signalled;
  os_handle  waitable_handle;
}

(a "waiter" is a helper which is how you add your "self" to the waitset; depending on the waitset implementation, waitable_handle might be your thread ID for example).

Then in the waitset notify you just do :


if ( w->signalled.exchange(true) == false )
{
   Signal( w->waitable_handle );
}
else
    step to next waiter in waitset and try him again.

That is, you try to only send the signal to handles that need it.

If we use this in the simple OR example from a few days ago, then both waiting threads will wake up - two notify_ones will wake two waiters.

While you're at it, your waiter struct may as well also contain the origin of the signal, like :


if ( w->signalled.exchange(true) == false )
{
    // non-atomic assignment :
    w->signal_origin = this; // this is a waitset
    Signal( w->waitable_handle );
}

That way when you wake from an OR wait you know why.

(note that I'm assuming your os_handle only ever does one state transition - it goes from unsignalled to signalled. This is the correct way to use waitset; each waiter() gets a new waitable handle for its lifetime, and it only lives for the length of one wait. In practice you actually recycle the waiters to avoid creating new ones all the time, but you recycle them safely in a way that you know they cannot be still in use by any thread (alternatively you could just have a waiter per thread in its TLS and reset them between uses))

(BTW of course you don't actually use atomic bool in real code because bool is too badly defined)

11-28-11 - Some lock-free rambling

2011-11-28T19:08:00.000-08:00

It helps me a lot to write this stuff down, so here we go.

I continually find that #StoreLoad scenarios are confusing and catch me out. Acquire (#LoadLoad) and Release (#StoreStore) are very intuitive, but #StoreLoad is not. I think I've covered almost this exact situation again, but this stuff is difficult so it's worth revisiting many times. (I find low level threading to be cognitively a lot like quantum mechanics, in that if you do it a lot you become totally comfortable with it, but if you stop doing it even for a month it is super confusing and bizarre when you come back to it, and you have to re-work through all the basics to convince yourself they are true).

(Aside : fucking Google verbatim won't even search for "#StoreLoad" right. Anybody know a web search that is actually verbatim? A whole-word-only option would be nice too, and also a match case option. You know, like basic text search options from like 1970 or so).

The classic case for needing #StoreLoad is WFMO. The very simple scenario goes like this :


bool done1 = false;
bool done2 = false;

// I want to do X() when done1 & done2 are both set.

Thread1:

done1 = true;
if ( done1 && done2 )
    X();

Thread2:

done2 = true;
if ( done1 && done2 )
    X();

This doesn't work.

Obviously Thread1 and Thread2 can run in different orders so done1 and done2 become set in random order. But one thread or the other should see them both set. But they don't; the reason is that the memory visibility can be reordered. This is a pretty clear illustration of the thing that trips up many people - threads can interleave both in execution order and in memory visibility order.

In particular the bad execution case goes like this :


done1 = false, done2 = false

T1 sets done1 = true
  T1 sees done1 = true (of course)
  T2 still sees done1 = false (store is not yet visible to him)

T2 sets done2 = true
  T2 sees done2 = true
  T1 still sees done2 = false

T1 checks done2 for (done1 && done2)
  still sees done2 = false
  doesn't call X()

T2 checks done1
  still sees done1 = false
  doesn't call X()

later
T1 sees done2=true
T2 sees done1=true

when you write it out it's obvious that the issue is the store visibility is not forced to occur before the load. So you can fix it with :


Thread1:

done1 = true;
#StoreLoad
if ( done1 && done2 )
    X();

As noted previously there is no nice way to make a StoreLoad barrier in C++0x. The best method I've found is to make the loads into fetch_add(0,acq_rel) ; that works by making the loads also be stores and using a #StoreStore barrier to get store ordering.

The classic simple waitset that we have discussed previously is a bit difficult to use in more complex ways.

Refresher : A waitset works with a double-check pattern, like :


signalling thread :

set condition
waitset.notify();

waiting thread :

if ( ! condition )
{
    waitset.prepare_wait()

    // double check :
    if ( condition )
    {
        waitset.cancel_wait();
    }
    else
    {
        waitset.wait();
    }
}

we've seen in the past how you can easily build a condition var or an eventcount from waitset. In some sense waitset is a very low level primitive and handy for building higher level primitives from. Now on to new material.

You can easily use waitset to perform an "OR" WFMO. You simply add yourself to multiple waitset. (you need a certain type of waitset for this which lets you pass in the primitive that you want to use for waiting). To do this we slightly extend the waitset API. The cleanest way is something like this :


instead of prepare_wait :

waiter create_waiter();
void add_waiter( waiter & w );

instead of wait/cancel_wait :

~waiter() does cancel/retire wait 
waiter.wait() does wait :

Then an OR wait is something like this :


signal thread 1 :

set condition1
waitset1.notify();

signal thread 2 :

set condition2
wiatset2.notify();


waiting thread :

if ( condition1 ) // don't wait

waiter w = waitset1.create_waiter();

// double check condition1 and first check condition2 :

if ( condition1 || condition2 ) // don't wait
  // ~w will take you out of waitset1

waitset2.add_waiter(w);

// double check :

if ( condition2 ) // don't wait

// I'm now in both waitset1 and waitset2
w.wait();

Okay. This works fine. But there is a limitation which might not be entirely obvious.

I have intentionally not made it clear if the notify() in the signalling threads is a notify_one (signal) or notify_all (broadcast). Say you want it to be just notify_one , because you don't want to make more threads than you need to. Say you have this scenario :


X = false;
Y = false;

Thread1:
X = true;
waitsetX.notify_one();

Thread2:
Y = true;
waitsetY.notify_one();

Thread3:
wait for X || Y

Thread4:
wait for X || Y

this is a deadlock. The problem is that both of the waiter threads can go to sleep, but the two notifies might both go to the same thread.

This is a general difficult problem with waitset and is why you generally have to use broadcast (for example eventcount is built on waitset broadcasting).

You may think this is an anomaly of trying to abuse waitset to do an OR, but it's quite common. For example you might try to do something seemingly simple like build semaphore from waitset.


class semaphore_from_waitset
{
    waitset_simple m_waitset;
    std::atomic<int> m_count;

public:
    semaphore_from_waitset(int count = 0)
    :   m_count(count), m_waitset()
    {
        RL_ASSERT(count >= 0);
    }

    ~semaphore_from_waitset()
    {
    }

public:
    void post()
    {
        m_count($).fetch_add(1,mo_acq_rel);
        // broadcast or signal :
        // (*1)
        //m_waitset.notify_all();
        m_waitset.notify_one();
    }

    bool try_wait()
    {
        // see if we can dec count before preparing the wait
        int c = m_count($).load(mo_acquire);
        while ( c > 0 )
        {
            if ( m_count($).compare_exchange_weak(c,c-1,mo_acq_rel) )
                return true;
            // c was reloaded
        }
        return false;
    }

    void wait(HANDLE h)
    {
        for(;;)
        {
            if ( try_wait() )
                return;
    
            // no count available, get ready to wait
            ResetEvent(h);
            m_waitset.prepare_wait(h);
            
            // double check :
            if ( try_wait() )
            {
                m_waitset.retire_wait(h);
                // (*2)
                // pass on the notify :
                m_waitset.notify_one();
                return;
            }
            
            m_waitset.wait(h);
            m_waitset.retire_wait(h);
            // loop and try again
        }
    }
};

it's totally straightforward in the waitset pattern, except for the broadcast issue. If *1 is just a notify_one, then at *2 you must pass on the notify. Alternatively if you don't have the re-signal at *2 then the notify at *1 must be a broadcast (notify_all).

Now obviously if you have 10 threads waiting on a semaphore and you inc the count by 1, you don't want all 10 threads to wake up so that just 1 of them can dec the count and get to execute. The re-signal method will wake 2 threads, so it's better than broadcast, but still not awesome.

(note that this is easy to fix if you just put a mutex around the whole thing; or you can implement semaphore without waitset; the point is not to reimplement semaphore in a bone-headed way, the point is to just that even very simple uses of waitset can break if you notify_one instead of notify_all).

BTW the failure case for semaphore_from_waitset with only a notify_one and no resignal (eg. if you get the (*1) and (*2) points wrong) goes like this :


the problem case goes like this :

    T1 : sem.post , sem.post
    T2&T3 : sem.wait

    execution like this :

    T2&3 both check count and see zereo
    T1 now does one inc and notify, noone to notify yet
    T2&3 do prepare_wait
    T2 does its double-check, sees a count and takes it (does not retire yet)
    T3 does its double-check, sees zero, and goes to sleep
    T1 now does the next inc and notify
    -> this is the key problem
    T2 can get the notify because it is still in the waiter list
        (not retired yet)
    but T3 needs the notify

The key point is this spot :


            // double check :
            if ( try_wait() )
            {
                // !! key !!
                m_waitset.retire_wait(h);

you have passed the double check and are not going to wait, but you are still in the waiter list. This means you can be the one thread chosen to receive the signal, but you don't need it. This is why resignal works.

11-25-11 - Sustainability

2011-11-25T02:00:00.000-08:00

I've always had a sour feeling about the "sustainability" movement, but I haven't been quite sure why exactly. As a knee-jerk reaction, I feel uneasy about any of the cultish movements where people get overly devoted to a narrow worldview, and tend to get into a dogma where adherence to the movement is more important than logically pursuing the original goals. So for example there are lots of current movements which I basically agree with, like "nose to tail" and "locavorism" and "minimalism" and so on, I think the basic ideas are great, but the movements themselves tend to be weird and actually kind of ruin the idea that I like so much by making it dogmatic.

(eg. if you eat pig's ears because you like pig's ears, that's cool. If you eat pig's ears because you got the whole pig and don't want to throw parts away, that's cool. If you eat pig's ears because you are trying to be a good "nose to tail"'er , that's fucking stupid.)

Anyhoo, I had a few realizations about what is that bothers me so much about "sustainability". First the obvious ones that I've known for a while :

"sustainability" is so expensive that it's only accessible to 10% of the population. When the vast majority of the population can't afford those products, they are inherently unsustainable, as in they do not support human life and they do not signficantly reduce the amount of factory farming , clear cutting , etc. A lifestyle which is only accessible to the rich cannot transform the earth.

The majority of "sustainable" products are unproven and may in fact not be sustainable, it's just a marketing word that doesn't correspond to any fact of actual low long-term impact on the earth. The fact is that the central valley of california and the fields of iowa have sustained "unsustainable" factory farming for the past 100 years or so, and despite predictions of imminent collapse, they are still feeding hundreds of millions of people for very low prices. On the other hand we get new coconut charcoal and bamboo or hemp or whatever which we don't really know how it will affect the earth in mass production on the long term.

Buying a bunch of new products because they are "sustainable" is of course highly ironic. The most destructive thing that modern society does is buy new junk every time there's a new trend, and this appears to be just another new trend, people throw out their unfashionable "unsustainable" stuff to buy new approved stuff, and will throw that out for the next trend. (also ironically, "minimalism" generally tends to involve buying new stuff).

High-paid low-yield gentleman farmers are inherently unsustainable. You cannot support a 7+ billion person planet with a good quality of life if the cost of a piece of lumber or a piece of fruit is so high and takes so much labor. Our quality of life (per capita) is entirely based on the fact that those things are so cheap and easy, so that we can spend more time producing TV shows and iPods. Now the more extreme hippie-ish end of the sustainability movement might espouse a true back-to-the-land lifestyle change where in fact people do spend more time laboring and don't get TV shows and iPods, but that is a small fringe, the main thrust wants the spoils of civilization.

Now a little equivocation. Buying "sustainable" junk is obviously a form of charity. When you spend much more on a "sustainable" version of a product, you are essentially donating the difference. Where does that donation go? Some (I suspect small) portion of it actually goes to benefiting the earth. Most of the rest goes to profit of the product maker. On that level, it is a very bad form of charity; your charity dollars would have a much greater direct benefit on the earth if you just bought normal products and donated the difference to direct action.

But it is a bit more complicated than that. For the most part I'm not delighted by exercising political expression through purchasing (it's far too easy to manipulate and take advantage of, and in the end the only thing that They care about is that you keep buying things like a good little consumer, so you really aren't winning) - however I can't deny that it does sometimes work. When industry sees that lots of consumers are willing to waste their dollars on "green" products, they do sometimes change their practices for the better, and the net result can be a greater impact than the amount of charity dollars suggest. That is, there is a sort of leverage if businesses think that the "political buyers" will continue spending lots of money far into the future, the businesses will make a change based on lots of *future* dollars. Thus something like only a few tens of millions of dollars in charity spending can actually create a hundred-million dollar product line transformation.

As an aside, I should note that there are lots of small scale "sustainable" endeavors that are basically irrelevant because they are inherently small scale and cannot ever have a significant effect on the planet. For example the reclaimed lumber movement, it's okay, I have no major objection to it (though it's not entirely clear that it's the best value for your charity lumber eco dollars), but it's just irrelevant to any large scale analysis because it can't significantly reduce commercial lumber use. The only sustainable businesses that matter are the ones that have the possibility to go large scale.

Anyhoo, the thing that occurred to me last night was that the large scale sustainable industry is basically built on the back of unsustainable industry.

What I mean is, the large-scale mass produced "sustainable" industry (eg. bamboo flooring, "sustainable" chocolate, etc) is largely about making products in the 3rd world and exporting them to the 1st world. First of all this is sort of inherently unsustainable and hypocritical because it relies on a massive income gap for affordability, essentially you have to have people in subsistence living conditions to subsidize this product, and a good liberal who is spending their charity dollars to direct the world towards a better future should not include that in their better future. But more directly, the workers in those sustainable factories could not live a decent life on their low wages without unsustainable industry. The only way they can be paid so low is because they can get cheap factory farm corn to eat, and cheap sneakers and clothes and everything they need to live. If they had to buy the expensive sustainable junk, they would have to have huge wages, which would make the product even more expensive, which would make it impossible.

11-23-11 - This is not okay

2011-11-23T02:00:00.000-08:00

Fuck this shit. I'm going to Hawaii.