Sort an array using only one local variable | Hacker News Reader

Sort an array using only one local variable

patrickmichaelsen.com

50 pointsnkurz18 comments

> When using a signed integer variable to represent an index, there is an entire range of negative numbers that are not useful at all. Let's make use of them, then.

If you have "local variable" with more bits than log(# elements to be sorted), then yes, this trick works, but with sufficient extra bits, you can pack multiple indexes into a single variable by shifting and 'or'ing.

An even sneakier way of hiding this extra bit is to use the program counter to store it:

  a:
    int i = 0
    FOR (; i < # elems-1; ++i)
         IF pair(i, i+1) is out of order
             swap pair; goto b
    RETURN
  b:
    FOR (; i < # elems-1; ++i)
         IF pair(i, i+1) is out of order
             swap pair
    GOTO a

If the program is running the "b" loop, some pair has been swapped, so when it finishes the loop, it knows to re-run the "a" loop. If the program completes the "a" loop, it knows no pair was swapped, and can finish.

Edit: formatting

That's the essence of a goto-based state machine (one of the few problems where gotos are the most natural solution), compared to the alternative of storing the state in a variable and doing an extra indirection every transition to "go to" the right one.

I guess you can move an arbitrary amount of booleans (or enums) into the running state.

I suppose that the very idea of variables is just to separate the state from the code so that it's possible to handle complex states in generic code with a reasonable size...

On the other hand, a lot of bugs are related to that the resulting implicit state machine is not complete and/or correct...

The same question but including the program state is the interresting one. How much information/state is needed and needs to be shared, as it relates to how an algorithm scales.

It's "one local variable" in the same way as

    struct {
        unsigned int theint:31;
        unsigned int thebool:1;
    } myvar;

and the code probably uses multiple CPU registers to do the abs(), the calculation of addresses for the XOR swap, etc. but still interesting just for the artificial constraint part of "can it be done".

Aside: this is one of those pages that shows everything but the actual post content(!) if you have JS disabled. And if you view the source code... you'll find a huge JSON object with the actual content, apparently just pure HTML embedded as a string inside it.

Note to readers: I am looking into a different platform for publishing my computer science articles. The current platform I am using is easy to use. However, it has its limitations. Not the least of which is the inability to use custom HTML where it is useful. This makes me unable to embed nice code snippets in my articles.

How about a simple HTML page?

the calculation of addresses for the XOR swap

I'd be interested to know more about the internal implementation, but I don't think that address calculation uses any additional registers (physical or logical). There are multiple execution ports dedicated to address generation, and I think they are self-contained.

multiple CPU registers to do the abs()

Likely yes for any library implementation, although this made me wonder if it's possible to do it in-place with constants. Turns out it is, Hacker's Delight to the rescue:

  abs(x) == ((x >>> 30) | 1) * x

http://hackersdelight.org/basics2.pdf

Thanks for putting the abs() part to rest. I included it for the sake of having the final code be a little more readable. But yes, indeed, it is possible once more to use bit-wise manipulation to achieve elegant solutions! Thanks for reading! And of course, thanks for posting this blog post, nkurz!

There's no memory-to-memory XOR in x86. A XOR swap will need one register, the array address itself will take another, and the "single integer variable" one more. Then you also need the absolute value of the variable; there's another register.

The single-expression abs that you specify needs at least two registers, one to hold the shifted value and one to hold the original one. Two alternatives which do not involve multiplication and are 3 instructions is here:

https://www.strchr.com/optimized_abs_function

The abs() trick works for storing one flag bit. But you can store more than one bit if you shift by N bits left and use the LSBs as flag/boolean bits (then circular shift right + mask when reading). You reduce the range of the local variable by a factor of 2 for every bit stored though (same as the abs trick). Tagged pointers use this method, but instead of shifting one can simply set/clear the bits due to implied alignment:

https://en.wikipedia.org/wiki/Tagged_pointer

Interesting! It never ceases to amaze me what tricks one can pull off with bit manipulation!

Thanks for reading!

As long as unused bits in our variables are fair game, the bool also has a minimum of 7 of them.

That's true. However, when coming up with creative solutions to problems, I think every unused bit is fair game! Thanks for reading!

I think it does not work on unsigned ints, it is also fairly slow.

I find External Merge Sort pretty interesting.

Interesting, I had never heard of External Merge Sort before. You are correct in that it does not work on unsigned ints and is unnecessarily slow.

An interesting alternative came to my attention in the form of "gnome sort". Gnome sort is also affectionately know as "stupid sort". It behaves similarly to bubble sort. Bubble sort "sinks" large elements which allows small elements to "bubble" up. Gnome sort, however, sinks large elements towards the end of the array AND sinks small elements towards the front of the array.

More on gnome sort: https://en.wikipedia.org/wiki/Gnome_sort

Once again, thanks for reading!

This site clips the content on smaller screens with no way to scroll it into view.

Thanks for letting me know! What device are you using to view the content?

I was using half a 4k screen (2x scaling). Making it full screen allowed me to see the whole page.

Cute. Could this be implemented as a compiler optimization for saving allocations?

I agree that it is cute! Unfortunately, it does not seem to have much of a practical use. If you're very curious, a professor at my school suggests testing out "how much memory is saved for compiler optimizations (like -O2 or -O3) for normal sorts vs this sort." You might be able to answer your question this way.

Thank you again, for reading! Cheers!

Reply on news.ycombinator.com