If you want to make an apple pie from scratch, you must first create the universe.
Carl Sagan

a little help with bitwise operators

August 3rd, 2015

Binary numbers are easy, right? You just do stuff with bits.

But invariably whenever I code C I can never remember how to actually set a bit or test a bit, I keep getting and and or confused.

So I made a cheat sheet I can look up any time. These are the key ones:

All the others are available on the cheat sheet.

so do you know how your program executes?

August 2nd, 2015

The answer is no, and here's why you shouldn't feel peer pressured into saying yes.

I was reading about disassembly recently when I came across this nugget:

(...) how can a disassembler tell code from data?

The problem wouldn't be as difficult if data were limited to the .data section of an executable and if executable code were limited to the .code section of an executable, but this is often not the case. (...) A technique that is often used is to identify the entry point of an executable, and find all code reachable from there, recursively. This is known as "code crawling".


The general problem of separating code from data in arbitrary executable programs is equivalent to the halting problem.

Well, if we can't even do *that*, what can we do?

We start with a program you wrote, awesome. We know that part. We compile it. Your favorite language constructs get desugared into very ordinary looking code - all the art you put into your program is lost! Abstract syntax tree, data flow analysis, your constants are folded and propagated, your functions are inlined. By now you wouldn't even know that it's the same program, and we're still in "high level language" territory (probably some intermediate language in the compiler). Now we get basic blocks and we're gonna lay them out in a specific order. This is where the compiler tries to play nice with the branch prediction in your cpu. Your complicated program aka "my ode to control flow" now looks very flat - because it's assembly code. And at last we assemble into machine code - the last vestiges of intelligent life (function names, variable names, any kind of symbolic information) are lost and become just naked memory addresses.

Between your program and that machine code... so many levels. And at each level there are ways to optimize the code. And all of those optimizations have just happened while you stared out the window just now.

So I started thinking about how programs execute. The fact is that predicting the exact execution sequence of a program, even in C, even in C 101 (no pointers, no threading) is basically impossible. Okay, I'm sure it's possible, but I'd have to know the details of my exact cpu model to have a chance.

I need to know how big the pre-fetch cache is. I bet there are some constants that control exactly how the out of order execution engine works - I need to know those. And I need to know the algorithms that are used there (like branch prediction, remember?). I need to know... oh shoot, multicore! Haha, multicore is a huge problem.

Basically, I need to know exactly what else is running on my system at this very time, because that's gonna wreak havoc with my caches. If my L1 gets hosed by another process that's gonna influence a load from memory that I was just about do. Which means I can't execute this instruction I was going to. So I have to pick some other instructions I have lying around and execute those speculatively while we wait for that delivery truck to return all the way from main memory.

Speculatively, you say? Haha yes, since we have these instructions here we'll just go ahead and execute them in case it turns out we needed to do that. Granted, a lot of what a cpu does is stuff like adding numbers, which is pretty easy to undo. "Oops, I 'accidentally' overwrote eax." I guess that addition never happened after all.

And then hyper threading! Do you know how hyper threading works? It's basically a way of saying "this main memory is so damn slow that I can simulate the execution of *two* different programs on a single core and noone's really gonna notice".

This whole thing gives rise to a philosophical question: what is the truth about your program? Is it the effect you observe based on what you read from memory and what you see in the registers (ie. the public API of the cpu)? Or is it the actual *physical* execution sequence of your instructions (the "implementation details" you don't see)?

I remember when virtual machines were starting to get popular around 2000 and there was a lot of discussion about whether they were a good thing - "think about the performance implications". Hell, our so-called physical machines have been virtual for a very long time already!

It's just that the cpu abstraction doesn't seem to leak very much, so you think your instructions are being executed in order. Until you try to use threads. And then you have to ask yourself the deep existential question: what is the memory model of my machine anyway? Just before you start putting memory barriers everywhere.

So no, you don't. But none of your friends do either (unless they work for Intel).

a paciência

July 20th, 2015

Você tem muita paciência? Eu não. Pelo menos não tinha. Desde criança fui sempre impaciente. Com quê? Com tudo. Sempre queria que as coisas acontecessem já, não gostava de esperar. Nunca gostava de esperar para seja que for.

Isso é bom? É mau? Pode ser bom. Pode ser mau.

Ser impaciente favorece a eficiência. Acho que não é coincidência ter-me tornado engenheiro. Os engenheiros gostam da eficiência. Gostam de soluções ótimas. Uma soluçao ótima quer dizer que não é possível fazê-lo mais rapidamente.

Ser impaciente tem muitas vantagens. Com a mentalidade impaciente a gente está sempre em busca de vitórias faceis. Torna-se a conseguir muitas pequenas coisas em pouco tempo, adotando sempre métodos simples. E não só se trata de obter sucessos, mas também de pesquisar e encontrar objetivos que podem ser conseguidos em pouco tempo. Muitas vezes a simplicidade não fica na solução que adotamos se não na escolha de um objetivo mais simples que todavia representa um benefício parecido. Sem isso é provável às vezes você dedicar muito mais tempo para resolver uma problema do que o necessário.

Apesar disso também existem inconvenientes em ser impaciente. Muitos objetivos na vida não são possíveis de conseguir em pouco tempo. Quais? Aprender idiomas por exemplo. Mesmo com um método ótimo a gente tem de passar centenas de horas, talvez milhares de horas. Eu comecei a aprender idiomas há cinco-seis anos. Antes só falava os meus idiomas nativos mais o inglês. Sempre quis falar francês mas achei que foi demasiado difícil domar a gramática. Fui impaciente, não conseguia continuar a estudar sem ver o efeito de progredir rapidamente. Portanto parei. E não fiz nada para aprender francês durante muitos anos.

Hoje em dia consigo muito melhor fazer coisas que exigem muito esforço. Acho que a única coisa que mudou foi eu tornar-me mais paciente.

waarom zijn de openingstijden zo gek?

July 13th, 2015

Ik heb een vraag: Hou je van zwemmen? Als wel dan ga je waarschinlijk in het zwembad zwemmen, toch?

En dan weet je het al, want het is onmogelijk het niet op te merken. De openingstijden van elk zwembad zijn gek. Helemaal gek. Ik snap er niets van.

Bij elke winkel, bibliotheek, postkantoor, restaurant en wat dan ook geldt hetzelfde: ze gaan ergens 's morgens openen en dan later, ergens 's avonds sluiten. Vrij simpel. Logisch.

Maar niet bij een zwembad. Want daar heb je allerlei verschillende soorten van zwemmen. Banen zwemmen. Vrij zwemmen. Familie zwemmen. Aquajogging. Wat dan ook.

En voor elke soort zwemmen zijn er andere openingstijden daarbij. Natuurlijk. Zeven uur openen. Half negen sluiten. Twaalf uur openen. Één uur sluiten. Vijf uur openen. Zes uur sluiten. Je heb geen één mogelijkheid om te zwemmen, je heb er een heleboel! Als je heel snel bent...

Bovendien zijn de openingstijden niet dezelfden elke dag, zeker niet! Maandag is er geen vijf tot zes. Dinsdag wel. Woensdag heb je ook negen tot tien, maar geen vijf tot zes meer.

Elk zwembad heeft andere openingstijden per soort zwemmen en die zijn anders elke dag. Behalve nu in de zomervakantie, want dan gaan enkele zwembaden sluiten. En ik bedoel volledig sluiten, tijdens enkele weken. En de anderen, die hebben natuurlijk wijzigde openingstijden, want het is zomer toch! Kan niet hetzelfde blijven.

Ik heb het een keer gevraagd aan de mevrouw bij de balie. "Dat moet u aan de mensen op kantoor vragen", zei ze. "Ik vind ook dat dat niet mag."

Is het zo overal in Nederland? Waarom, in godsnaam?

a coragem existe?

July 4th, 2015

Há algumas semanas, eu refleti sobre isto.

É que não estou certo do conceito de coragem verdadeiramente representar uma coisa real. Porque não?

Quando é que se diz que alguém foi corajoso? Acho que acontece quando alguém faz alguma coisa que nós não poderíamos fazer, algo que percebemos ser demasiado arriscado. Então poderíamos fazê-lo se realmente quiséssemos fazê-lo?

Vamos ver um exemplo. Num dia de inverno, um homem caminhava perto dum rio. O rio foi parcialmente coberto pelo gelo, estava tão frio. Então, viu uma pessoa a flutuar no rio, que provavelmente caiu no rio acidentalmente. Foi claro que a pessoa não ia conseguir salvar-se, a água era tão fria e a corrente tão forte que precisava de muita força para conseguir sair delá. O homem decidiu ajudar, saltou no rio e nadou até a pessoa. Tirou-a do rio e chamou para uma ambulância. A pessoa foi salvada e não foi prejudicada.

Bem, o assunto é este. Então você decidiria fazer o mesmo? Acho que não, tendo em conta que este tipo de decisão é muito incomun. É por isso que a chamamos, um ato corajoso.

Mas que quer isso dizer? Quer dizer que, quando ouvimos este assunto achamos que o ato foi tão perigoso que nós nunca faríamos uma coisa parecida. O homem poderia ter morrido! Apesar disso, ele o fez! É aqui que encontramos o conceito de coragem. Ele fez aquilo, eu não poderia fazê-lo, portanto ele foi muito corajoso.

Até agora tudo bem.

Então quando se entrevista pessoas que tenham feito algo corajoso é comum dizerem que não foi uma decisão bem considerada. Foi uma decisão instintiva, sem refletir realmente nisso. Acho que isso quer dizer mesmo para a pessoa não é questão de coragem, é questão de fazer uma coisa que parece possível. Não nego a presenca duma preocupação, e do medo, mas apesar disso não impede a açao.

Acho que a explicaçao mais simples é que o ato parece muito mais arriscado para nós que para a pessoa que o fez. Para nós parece impossível, mas para a pessoa que o fez parece muito arriscada mas possível.

Gostamos de pensar que a coragem trata-se de vencer o medo e que teoricamente tudo é possível para todos. Então psicologicamente não o é. Existem atos que não conseguimos forçar-nos a fazer. A coragem descreve as differenças psicologicas entre pessoas, não demonstra que somos capaz de fazer qualquer coisa se apenas o quisermos.