Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Assembly Gems

dflund.se

Post reply on HN
Print view View original

1–10 of 14 posts

Re: Assembly Gems

#4

Post by userbinator »

I think this is one of the more interesting ones for its extreme terseness and opaqueness:

http://dflund.se/~john_e/gems/gem003a.html

It would be a little adventure to try to figure out how it was conceived, as although it looks like something a superoptimiser would produce, it was around before superoptimisation, and I think it was generated by a human likely related to the demoscene.

Re: Assembly Gems

#5

Post by billforsternz »

userbinator wrote: post #4

I think this is one of the more interesting ones for its extreme terseness and opaqueness: http://dflund.se/~john_e/gems/gem003a.html It would be a little adventure to try to figure out how it was conceived, as although it looks like something a superoptimiser would produce, it was around before superoptimisation, and I think it was generated by a human likely related to the demoscene.

This was a well known trick for 8080s and Z80s as far back as the 1970s. Back then there were a lot of assembly programmers, tricks like this were stock in trade.

Re: Assembly Gems

#7

Post by dr_zoidberg »

uxcn wrote: post #2

How many of these are still relevant? x86 has an instruction for crc , bswap , as well as nop now.

Now almost every code to be run is cache-bound for performance, not cycle-bound. So this gems, while may still work, may not be the best means to achieve optimal performance. Optimizing cache access is what brings the biggest speedups today -- see for example NumExpr[1].

[1] https://github.com/pydata/numexpr

Re: Assembly Gems

#8

Post by bro-stick »

billforsternz wrote: post #5
userbinator wrote: post #4

I think this is one of the more interesting ones for its extreme terseness and opaqueness: http://dflund.se/~john_e/gems/gem003a.html It would be a little adventure to try to figure out how it was conceived, as although it looks like something a superoptimiser would produce, it was around before superoptimisation, and I think it was generated by a human likely related to the demoscene.

This was a well known trick for 8080s and Z80s as far back as the 1970s. Back then there were a lot of assembly programmers, tricks like this were stock in trade.

Reminds me of optimizing microcode back in uni... From the reference implementation of 134 microinstructions down to 61, and it was far more cycle-efficient as well (progressive decoding and Huffman encoded micro representation given sample programs). Since it was a contest for two goals of extra credit, people were pissed that our team captured both. It took about 30 hours to implement.

Microinstructione are like a CPU's firmware which implements the external-facing macroinstruction set into a simpler set of microinstructions which coordinate various internal state.

Re: Assembly Gems

#9

Post by uxcn »

dr_zoidberg wrote: post #7
uxcn wrote: post #2

How many of these are still relevant? x86 has an instruction for crc , bswap , as well as nop now.

Now almost every code to be run is cache-bound for performance, not cycle-bound. So this gems, while may still work, may not be the best means to achieve optimal performance. Optimizing cache access is what brings the biggest speedups today -- see for example NumExpr[1]. [1] https://github.com/pydata/numexpr

Cache is extremely important, but most of these operate strictly on values in registers. So, losing cycles due to cache misses, latency, contention, etc... isn't a bottleneck.

A lot of these are crucial enough that they've been codified in transistors now, and generally can execute in a cycle without consuming extra registers. There are still some very valid bit tricks though.

Re: Assembly Gems

#10

Post by psykotic »

Here's a little gem that I don't see mentioned on there.

For bit unpacking in C, the natural inclination is to shift out the least significant bit with something like this:

    u1 getbit() { u1 lsb = x & 1; x >>= 1; return lsb; }
However, most assembly languages have a better alternative if you instead shift out the most significant bit. Suppose that the bit buffer is in ECX. Then you would do ADD ECX, ECX to left shift ECX and (this is the important part) put the shifted-out bit into the carry flag. From there the carry flag can be shifted into the least significant bit of another register, say EAX, with ADC EAX, EAX, or you can branch based on the carry with JC/JNC

As a full example, here is the gamma decoder from apack/aplib, which despite its simplicity rewards careful study:

    getbit:
        add    dl, dl
        jnz    .stillbitsleft
        mov    dl, [esi]
        inc    esi
        adc    dl, dl
      .stillbitsleft:
        ret

    getgamma:
        xor    ecx, ecx
    getgamma_no_ecx:
        inc    ecx
      .getgammaloop:
        call   getbit
        adc    ecx, ecx
        call   getbit
        jc     .getgammaloop
        ret
Post reply on HN