Old O'Reilly X books

[Matt Turner]

On Thu, Aug 26, 2010 at 11:11 AM, Aaron Plattner <aplattner at nvidia.com> wrote:
> On Thu, Aug 26, 2010 at 05:43:53AM -0700, Pat Kane wrote:
>> BTW, while trying to grep my dead trees I noticed that the current X server
>> contains some HAKMEM code, in ./mi/micmap.c I see this hack:
>>     ...
>>     count = (visuals >> 1) & 033333333333;
>>     count = visuals - count - ((count >> 1) & 033333333333);
>>     count = (((count + (count >> 3)) & 030707070707) % 077);  /* HAKMEM 169 */
>>     ...
>
> Hah, awesome.
>
> Apparently that code sucked in 1995 and still sucks today:
> http://compilers.iecc.com/comparch/article/95-07-080
>
> I increased the loop count by two orders of magnitude:
>
> NAIVE:    5.616 sec
> HAKMEM:   7.541 sec
> HAKMEM_P: 8.381 sec

There are lots of interesting articles on this subject, one of which
is http://www.dalkescientific.com/writings/diary/archive/2008/07/03/hakmem_and_other_popcounts.html

There was also a thread on mesa-dev called "minor u_math.h speedup
fun" on 11/28/09 that's worth reading.

Matt