4 ms·

Sort an array using only one local variable

50 points by nkurz 11y ago

deleted 11y ago
[deleted]
jmiserez 11y ago
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 https://en.wikipedia.org/wiki/Tagged_pointer
- prmichaelsen 11y ago
  Interesting! It never ceases to amaze me what tricks one can pull off with bit manipulation! Thanks for reading!
furyofantares 11y ago
As long as unused bits in our variables are fair game, the bool also has a minimum of 7 of them.
- prmichaelsen 11y ago
  That's true. However, when coming up with creative solutions to problems, I think every unused bit is fair game! Thanks for reading!
deleted 11y ago
[deleted]
thelema314 11y ago
> 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
- userbinator 11y ago
  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.
- kpil 11y ago
  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.
trollingineeer 11y ago
You'd be a great interviewer at Google!
userbinator 11y ago
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?
- nkurz 11y ago
  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 http://hackersdelight.org/basics2.pdf
  - prmichaelsen 11y ago
    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!
    - deleted 11y ago
      [deleted]
jkot 11y ago
I think it does not work on unsigned ints, it is also fairly slow. I find External Merge Sort pretty interesting.
- prmichaelsen 11y ago
  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 https://en.wikipedia.org/wiki/Gnome_sort Once again, thanks for reading!
mwsherman 11y ago
Cute. Could this be implemented as a compiler optimization for saving allocations?
- prmichaelsen 11y ago
  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!
kevincox 11y ago
This site clips the content on smaller screens with no way to scroll it into view.
- prmichaelsen 11y ago
  Thanks for letting me know! What device are you using to view the content?
  - kevincox 11y ago
    I was using half a 4k screen (2x scaling). Making it full screen allowed me to see the whole page.

50 points by nkurz 11y ago

deleted 11y ago

[deleted]

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 https://en.wikipedia.org/wiki/Tagged_pointer

prmichaelsen 11y ago
Interesting! It never ceases to amaze me what tricks one can pull off with bit manipulation! Thanks for reading!

furyofantares 11y ago

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

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

deleted 11y ago

[deleted]

thelema314 11y ago

> 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

userbinator 11y ago
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.
kpil 11y ago
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.

trollingineeer 11y ago

You'd be a great interviewer at Google!

userbinator 11y ago

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?

nkurz 11y ago
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 http://hackersdelight.org/basics2.pdf
- prmichaelsen 11y ago
  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!
  - deleted 11y ago
    [deleted]

jkot 11y ago

I think it does not work on unsigned ints, it is also fairly slow. I find External Merge Sort pretty interesting.

prmichaelsen 11y ago
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 https://en.wikipedia.org/wiki/Gnome_sort Once again, thanks for reading!

mwsherman 11y ago

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

prmichaelsen 11y ago
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!

kevincox 11y ago

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

prmichaelsen 11y ago
Thanks for letting me know! What device are you using to view the content?
- kevincox 11y ago
  I was using half a 4k screen (2x scaling). Making it full screen allowed me to see the whole page.