Fun with UB in C: returning uninitialized floats

The average C/C++ programmer's intuition says that uninitialized variables are fine as long as you don't depend on their values.

A more experienced programmer probably suspects that uninitialized variables are fine as long as you don't access them. That is, computing c=a+b where b is uninitialized is not harmless even if you never use c. That's because the compiler could, say, optimize away the entire block of code surrounding c=a+b under the assumption that c=a+b, where b is proven to be always uninitialized, is always undefined behavior (UB). And if it's UB, the only way for the program to be correct is for this code to be unreachable anyway. And if it's unreachable, why waste instructions translating any of it?

However, the following code looks like it could potentially be OK, doesn't it?

float get(obj* v, bool* ok) {
  float c;
  if(v->valid) {
    *ok = true;
    c = v->a + v->b;
  else {
   *ok = false; //not ok, so don't expect anything from c
  return c;

Here you return an uninitialized c, which the caller shouldn't touch because *ok is false. As long as the caller doesn't, all is well, right?

Well, it turns out that even if the caller does nothing at all with the return value – ever, regardless of *ok – the program might bomb. That's because c could be initialized to a singaling NaN, and then say on x86, when the fstp instruction is used to basically just get rid of the return value, you get an exception. In release mode but not in debug mode, some of the time but not all the time. This gives you this warm, fuzzy WTF feeling when you stare at the disassembled code. "Why is there even a float here in the first place?!"

How much uninitialized data is shuffled around by real-world C programs? A lot, I wager – likely closer to 95% than to 5% of programs do this. Otherwise Valgrind would not go to all the trouble to not barf on uninitialized data until the last possible moment (that moment being when a branch is taken based on uninitialized data, or when it's passed to a system call; to not barf then would require some sort of a multiverse simulation approach for which there are not enough computing resources.)

Needless to say, most programs enjoying ("enjoying"?) Valgrind's (or rather memcheck's) conservative approach to error reporting were written neither in assembly which few use, nor in, I dunno, Java, which won't let you do this. They were written in C and C++, and most likely they invoke UB.

(Can you touch uninitialized data in C without triggering UB? I seriously don't know, I'm not a language lawyer. Being able to do this is actually occasionally useful for optimization. Integral types for instance don't have anything like signaling NaNs so at the assembly language level you should be fine. But at the C level the compiler might get needlessly clever if it manages to prove that the data is uninitialized. My own intuition is it can never prove squat about data passed by pointer because of aliasing and so I kinda assume that if I get a buffer pointing to some data and some of it is uninitialized I can do everything to it that I could in assembly. But I'm not sure.)

What a way to make a living.



Accidentally quadratic: rm -rf??

This is a REALLY bad time. Please please PLEASE tell me I'm not fucked…

I've accidentally created about a million files in a directory. Now ls takes forever, Python's os.listdir is faster but still dog-slow – but! but! there's hope – a C loop program using opendir/readdir is reasonably fast.

Now I want to modify said program so that it removes those files which have a certain substring in their name. (I want the files in that directory and its subdirectories, just not the junk I created due to a typo in my code.)


O(N^2) is easy enough. The unlink function takes a filename, which means that under the hood it reads ALL THE BLOODY FILE NAMES IN THAT DIRECTORY until it finds the right one and THEN it deletes that file. Repeated a million times, that's a trillion operations – a bit less because shit gets divided by 2 in there, but you get the idea.

Now, readdir gives me the fucking inode number. How the FUCK do I pass it back to this piece of shit operating system from hell, WITHOUT having it search through the whole damned directory AGAIN to find  what it just gave me?

I would have thought that rm -rf for instance would be able to deal with this kind of job efficiently. I'm not sure it can. The excise function in the guts of coreutils for instance seems to be using unlinkat which gets a pathname. All attempts to google for this shit came up with advice to use find -inode -exec rm or some shit like that, which means find converts inode to name, rm gets the name, Unix converts the name back to inode…

So am I correct in that:

  • Neither Unix nor the commercial network filers nor nobody BOTHERS to use a hash table somewhere in their guts to get the inode in O(1) from the name (NOT A VERY HARD TASK DAMMIT), and
  • Unix does not provide a way to remove files given inode numbers, but
  • Unix does unfortunately makes it easy enough (O(1)) to CREATE a new file in a directory which is already full of files, so that a loop creating those bloody files in the first place is NOT quadratic?? So that you can REALLY shoot yourself in the foot, big time?

Please tell me I'm wrong about the first 2 points, especially the second… Please please please… I kinda need those files in there…

(And I mean NOTHING, nothing at all works in such a directory at a reasonable speed because every time you need to touch a file the entire directory is traversed underneath… FUUUUUCK… I guess I could traverse it in linear time and copy aside somehow though… maybe that's what I'd do…)

Anyway, a great entry for the Accidentally Quadratic blog I guess…

Update: gitk fires up really damn quickly in that repository, showing all the changes. Hooray! Not the new files though. git citool is kinda… sluggish. I hope there were no new files there…


  • `find fucked-dir -maxdepth 1 -name "fuckers-name*" -delete` nuked the bastards; I didn't measure the time it took, but I ran it in the evening, didn't see it finish in the half an hour I had to watch it, and then the files were gone in the morning. Better than I feared it would be.
  • As several commenters pointed out, many modern filesystems do provide O(1) or O(log(N)) access to files given a name, so they asked what my file system was. Answer: fucked if I know, it's an NFS server by a big-name vendor.
  • Commenters also pointed out how deleting a file given an inode is hard because you'd need a back-link to all the directories with a hard link to the file. I guess it makes sense in some sort of a warped way. (What happens to a file when you delete it by name and there are multiple hard links to it from other directories?.. I never bothered to learn the semantics under the assumption that hard links are, um, not a very sensible feature.)

"Information asymmetry" cuts both ways

They pretend to pay us, and we pretend to work.












Basically the "knowledge worker's" contract is something like this:








A "WTF is that sound" widget

A core function of an OS is dividing resources between apps: multiple windows per screen, files per disk, sockets per Internet connection, etc.

The machine's goddamned SPEAKER is one of those resources.

Now let's say you're working at your desktop. Your boss walks in for a chat. And now, midway through the conversation, your computer's goddamned speaker emits something like: "Major breakthrough reached at the G-20 meeting!", or "I came in like a wrecking ball!", or "Aaaah… ah! yeah, right there… AAAGH!!"

Your computer might have said it because you're watching news, or that other stuff, instead of working. Alternatively, perhaps some uninvited pop-up popped up an hour earlier - and then decided to self-activate at the worst possible moment.

Either way, it'd be nice to be able to shut the thing off quickly – say, right after "Hi, I'm Wendy" and before it gets to "yeah, right there." And not only that, but you might want to kill the app without giving focus to its window, because who knows what Wendy's up to in that window.

Now, closing a window or deleting a file is easy, because you have a visible handle to click on. Not so with sound, unfor-tu-nate-ly. Big mistake on behalf of OS designers, says I… BIG MISTAKE.

And that, folks, is the perfect use case for a "WTF is that sound" widget. I haven't figured it out down to an actual mockup or anything, but, ya know, it'd be a list of who the FUCK is using the GODDAMNED SPEAKER. "Who the fuck" might be a list of window titles – or maybe not, because you might not want a title like "Erm erm Wendy erm ahem". So it might be a list of app names without the window titles. Most importantly, if just ONE app is using the goddamned speaker, then there'd be just one red button that you press to KILL the fucking thing.

I'm hereby placing the idea in the public domain. Now go ahead and make {the world a better place, billions, an abandoned GitHub project implementing this dumb idea}.

P.S. I'm fine, thank you, but yes, the inspiration comes from real life, and no, it was neither Miley Cyrus nor Wendy, but a weird tune without words that ended as mysteriously as it commenced, and I still don't know what played it.

Update: no, it's not like a mute button. If we're seriously being serious about it, then pressing a mute button is like turning off the screen. When the boss walks in and there's a noise and you mute everything including the ambient music it's off, just like pressing the screen's off button would be off. More seriously, if you have umpteen apps and tabs and shit and something starts to emit sound and you don't know what that is, then a mute button doesn't help you, not if you want to listen to anything else at the same time which you might want to. So you need a "sound manager" just like you need a window manager. (Imagine having to guess which of the umpteen [x] buttons to close to make a particular window disappear. Sucks, right? Exactly the situation with sound, which, if it doesn't happen to be synced to video playing in some window, comes from fuck knows where – and even if it's synced to video, you must sift through windows to find that video! Why can't the window/tab/whatever at least have an indication of "sound is being emitted by the sucker who opened me"? Seriously, it's just dumb.)

A Sokoban levels design programming contest

I hate puzzles with a passion; I think of them as Gordian knots best untied with a sword, a machine gun or whatever else you can bring to bear on the problem.

The world of computer programmers, however – the world which I entered with the sole purpose of working for the highest bidder – is a world full of people who sincerely love puzzles. And if you visit this blog, perhaps you're one of these people.

If so, you might be pleased to learn about the recently launched Sokoban levels design contest, operated by gild – a great hacker, my long-time co-worker, an IOCCC winner, and a participant in Al Zimmerman's programming contests which he cites as inspiration for his own new contest.

The rules are precisely defined here; the general idea is to design Sokoban levels falling into different problem classes. Submitted levels are scored based on the length of the shortest solution (longer is better), and normalized s.t. the level taking the most steps to solve right now gets the score of 1. With 50 problem classes, the maximal overall score is 50. But with all the other cunning contestants submitting their own levels, your levels' score might be dropping every day or hour!

And I really mean every day or hour – even now at the very beginning there are several submissions per day. Judging by the rankings page, people spread around the globe are busy improving their Sokoban level-designing software and resubmitting better solutions. (Or they might be doing it in their heads; you don't need to submit any code, just the levels. I hear that occasionally a contestant using no software at all gets a rather good result in an Al Zimmerman's contest… What happens inside the heads of such people I don't know.)

There's also a discussion group, and if you're among the cunningest, most tenacious puzzle lovers who'll get to the top, you'll get – guess what? – a puzzle! Specifically, a gift card which you can use to buy, say, this Rubik's cube – or rather a Rubik's fuck-knows-what. I guess cubes are for sissies:

I personally think it's a bloody cool community/subculture to be in; a pity that I don't quite have the brains for it. (Could I hold my own if I really liked it? Or maybe I would really like it if I could hold my own? These are the types of questions it all brings to my mind.)

Anyway – if you're that sort of guy, it looks like a great thing for your brain to chew on. Good luck!

We're hiring

On behalf of easily the hottest computer company in Israel right now (self-driving cars, big noisy IPO, etc. etc.), I'm looking for people in the two areas I'm involved with:

  • software infrastructure / host tools
  • chips / hardware-software co-design

If you're a strong programmer, especially one who's also interested in math/vision/learning or low-level/hardware/optimization or both, you'll probably find enjoyable stuff to do. It looks like there's still plenty of room for growth, which usually means a lot of work to choose from. On the other hand, there's no risk of "wasting" your effort on a product which might never ship.

If you aren't a programmer but a hardware hacker (experienced in ASIC/FPGA or just straight out of school), we're hiring for these positions as well – I'll forward your CV to the relevant people.

People who work autonomously are a great fit, and they tend to like us - we gladly dial the extent of management down to near-zero levels when appropriate.

Also, I'd love to find people who tend to be at the center of things working with others – though there's always something in stock for people who'd rather spend time alone with a worthy problem.

Relevant experience – might be a plus of course, but not a must.

Send email to, and tell your friends. Seriously, one never knows and it's kinda awkward to sell vaguely described positions at a personal blog, but I think it can be a really nice opportunity.

Update: I should mention that we're in Jerusalem and while working from another location is not impossible, it's an extremely rare arrangement. So if you don't plan to relocate and send your resume nonetheless, I might have nothing to offer even though you sent a perfectly good one.

(It so happens that most resumes come from abroad. Blogging in Hebrew would make posts about open positions more effective, I guess; it turns out that people tend to mostly read in their mother tongue. I find it rather weird – I mean when it comes to computing where the terminology and even the code is in English, so writing about it in another language is invariably awkward. The fact remains, however, that most of my readers are from the US and the UK… Had the British Empire conquered four quarters of the world instead of just one, certainly language-wise life would have been simpler for us all.)

Capital vs labor: who risks more?

AFAIK, in the developed world, the income tax rate is often higher than the capital gains tax. In particular, income is taxed "progressively", meaning that higher income results in a higher rate – which doesn't always happen with capital gains. (It looks like it does happen in the US, but income appears to be taxed "more progressively".)

One justification for this is that investors risk losing much or all of their capital. Workers, on the other hand, are guaranteed their wages. To some extent, the difference in the tax rates compensates for the difference in the risks.

To me this is sensible at first glance but completely harebrained on second thought:

  • The worker's big risk is choosing the profession. Higher-income professions often require a more expensive education. If the demand for the skills drops in the future, the income might fail to cover the worker's investment into acquiring these skills. Assuming that learning ability drops with age, the risk increases proportionately.
  • Moreover, this risk is not diversified. Even a small-time investor can spread his risk using some sort of index fund, betting on many stocks at a time. For a worker, on the other hand, there's no conceivable way to be 25% lawyer, 25% carpenter, 25% programmer and 25% neurosurgeon.

The latter point may not interest utilitarian economists focused on GDP "the greatest good for the greatest number" – for society as a whole, risk is always diversified, even if Joe Shmoe is stuck with the crummiest profession that looked really promising when he chose it. Moreover, an efficient market would provide a way to insure against the risk of poorly choosing your occupation. (I don't think real-life markets did provide such a thing, though I might be mistaken.)

But the first point – that the risk exists, and that it's more likely than not to be proportionate to the projected income – by itself kinda erodes the ground underneath an income tax higher than the capital gains tax, not? I mean, regardless of the motivation, it seems internally inconsistent. Unless the risks are all quantified and it all magically cancels out.

It's not that I'm complaining – unlike most professionals, we programmers get stock options. (Speaking of which - central bankers of the world, The Programmers' Guild says thanks a bunch for QE and ZIRP! Remind us to send some flowers.) I just honestly don't get it.

Econ-savvy readers: what do I miss?

(Please don't accuse me of failing to use the Google. Maybe I did so badly, but I did try using the Google. The Google told me, for instance, that the optimal capital gains tax is zero, because "you can't transfer from capitalists to workers", because the transfer depletes the capital pool or something. But I didn't understand how it accounts for the case where the workers are also capitalists because they invest their savings; and what if there's a progressive tax on capital gains? Is it, or is it not possible to "transfer from capitalists to workers" the flesh and blood people, as opposed to abstract categories, regardless of whether you'd want to? Or if that's all nonsense – then is the optimal income tax also zero, because, hey, you're actually taxing human capital gains? Bringing us back a couple hundred years ago where we just have a sales tax? And again, not that I'd complain, I just don't quite follow the logic.)

(Also from the Google there's the claim that since nominal capital gains are taxed, the tax rate is actually higher than it looks because of inflation. But then the solution would be to tax inflation-adjusted gains, not to lower the rate arbitrarily, not? Also, wages are AFAIK the last set of prices to rise upon inflation – the "stickiest" – so workers' investment in their skills is continuously nibbled at by inflation as well. And the point made about "discouraging savings" – well, a high income tax discourages costly education and the subsequent ongoing investment in one's skills, which is a form of investment/savings/call it what you like. Same diff.)

I think it's pretty obvious that workers risk much more than investors. Whether this should lower their taxes I don't know, but it sort of makes sense to me.

Do company names actually matter?


  • Twitter: another one-product company.


  1. The company name often reflects founders' vision.



A better future (a programmer's first animated post)









Why is it so hard?







I like getting paid, I must admit despite the embarrassment.













  1. I program because they pay me.
  2. Programming is good because they pay me.
  3. Programming is good.



















"What?! But, the money -"


"How much is enough?" asked self.

Now he really got me worked up.










Sorry for having published a draft

I've just unpublished it.

Yikes. You know what's a good metaphor for a draft? Someone's undressed self who in a less than fully awake state makes uncertain steps towards the toilet. That's a first draft of that person's publicly presentable self.

And publishing a draft? It's a bit like being photographed in this state. I mean, we all pass through that state every morning. Nothing to be ashamed of, then. And yet.

I think a lot of RSS aggregators never delete a published post, even if it then disappears from the up-to-date RSS stream of the original site. Bastards. Someone should spread their naked morning photos all over the internet and see how they like it.

Anyway, sorry, and the finished thing (10 times shorter without all the written-then-thrown-away bits) is coming up soon.