Monday, February 28, 2011

Hacker's Delight: reversing bits

0 comments
From "Hacker's Delight" book, how to reverse bits elegantly:
x = (x & 0x55555555) <<  1 | (x & 0xAAAAAAAA) >>  1;
x = (x & 0x33333333) <<  2 | (x & 0xCCCCCCCC) >>  2;
x = (x & 0x0F0F0F0F) <<  4 | (x & 0xF0F0F0F0) >>  4;
x = (x & 0x00FF00FF) <<  8 | (x & 0xFF00FF00) >>  8;
x = (x & 0x0000FFFF) << 16 | (x & 0xFFFF0000) >> 16;

An slightly more efficient version:
x = (x & 0x55555555) <<  1 | (x & 0xAAAAAAAA) >>  1;
x = (x & 0x33333333) <<  2 | (x & 0xCCCCCCCC) >>  2;
x = (x & 0x0F0F0F0F) <<  4 | (x & 0xF0F0F0F0) >>  4;
x = (x << 24) | ((x & 0xFF00) << 8) | 
      ((x >> 8) & 0xFF00) | (x >> 24);

And this last line gives you byte reversal:
x = (x << 24) | ((x & 0xFF00) << 8) |
      ((x >> 8) & 0xFF00) | (x >> 24);

Sunday, February 20, 2011

SEDA architecture

0 comments
Not long ago, I worked on system that, in a way, resembled SEDA architecture. Although I had attended SOSP '01 and attended Matt Welsh's presentation on SEDA, I couldn't remember much about it so many years later. At the time, I did not connect the dots, but a Principal Engineer mentioned it and quickly I reminded myself about SEDA. Today I read an article explaining it and also a Matt's restrospective on SEDA that I wanted to share with you:

http://muratbuffalo.blogspot.com/2011/02/seda-architecture-for-well-conditioned.html
http://matt-welsh.blogspot.com/2010/07/retrospective-on-seda.html

Matt's retrospective is interesting as the architecture is something that he stills sees a valid and worth considering for modern system, but the stages is something he would group to reduce latency. I would say that, from my experience, the issue is how to have the proper visibility into each stage and its queues, to understand how the system is behaving. Sometimes one just butt heads due to the lack of understanding of the overall architecture and due to lack of metrics on where your backlog may be to understand your bottleneck.

One great question about this retrospective is how Matt views Actors (as in Scala)? The poster asks whether each actor could be a sort of micro-stage in a SEDA architecture. Unfortunately Matt hasn't replied to this question (yet).

Tuesday, February 08, 2011

Queueing Theory Books On Line

0 comments
Good list of books online on queueing theory:
http://web2.uwindsor.ca/math/hlynka/qonline.html