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

Lomuto's Comeback

dlang.org

Post reply on HN
Print view View original

101–104 of 104 posts

Re: Lomuto's Comeback

#101

Post by tom_mellior »

ncmncm wrote: post #58
tom_mellior wrote: post #22

Earlier quoted context omitted.

32-bit ARM assembly language provided conditional execution for most instructions. This was dropped in the 64-bit instruction set. ( https://en.wikipedia.org/wiki/Predication_(computer_architec... , https://en.wikipedia.org/wiki/ARM_architecture#64-bit ) I imagine the architects had a clear picture of the advantages and disadvantages, and made a very well-informed decision. I guess that part of the reason might have…

You can get close to the performance of a cmov instruction by generating a pair of all-1s and all-0s values: a=c, b=c-1, and a result z=a&x|b&y. Gcc will not under any circumstances produce two cmov instructions in a basic block, so that is your only alternative without dropping to asm. Clang is happy to produce two adjacent cmov instructions. Usually your ALUs are not otherwise so engaged as to make the number of op…

I don't get this. If c can be 0 or 1, then a can be 0 or 1, so it can be all-0s but not all-1s. b can be -1 or 0, so that part is fine. Can you show actual C or C++ code for a function like this:

    int select(int x, int y, bool condition) {
        ...
    }

Re: Lomuto's Comeback

#102

Post by ncmncm »

tom_mellior wrote: post #101
ncmncm wrote: post #58

Earlier quoted context omitted.

You can get close to the performance of a cmov instruction by generating a pair of all-1s and all-0s values: a=c, b=c-1, and a result z=a&x|b&y. Gcc will not under any circumstances produce two cmov instructions in a basic block, so that is your only alternative without dropping to asm. Clang is happy to produce two adjacent cmov instructions. Usually your ALUs are not otherwise so engaged as to make the number of op…

I don't get this. If c can be 0 or 1, then a can be 0 or 1, so it can be all-0s but not all-1s. b can be -1 or 0, so that part is fine. Can you show actual C or C++ code for a function like this: int select(int x, int y, bool condition) { ... }

Sorry, brain freeze. See

https://news.ycombinator.com/item?id=23237663

The bitwise thing is correctly -c&x|(c-1)&y.

Re: Lomuto's Comeback

#103

Post by ncmncm »

ncmncm wrote: post #57

It is true that more swaps may be cheaper than fewer swaps. The operations to count, nowadays, are not swaps or comparisons, which are very cheap, but instead pipeline stalls, which are very, very expensive. It is easy to better-than-double the speed of vanilla quicksort with a three-line change in the partition step.

Details

https://news.ycombinator.com/item?id=23237663

Re: Lomuto's Comeback

#104

Post by tom_mellior »

ncmncm wrote: post #102
tom_mellior wrote: post #101

Earlier quoted context omitted.

I don't get this. If c can be 0 or 1, then a can be 0 or 1, so it can be all-0s but not all-1s. b can be -1 or 0, so that part is fine. Can you show actual C or C++ code for a function like this: int select(int x, int y, bool condition) { ... }

Sorry, brain freeze. See https://news.ycombinator.com/item?id=23237663 The bitwise thing is correctly -c&x|(c-1)&y.

Oh, yes, I should have realized that -c is enough to transform from 0/1 to 0/-1. Thanks!
Post reply on HN