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

91–100 of 104 posts

Re: Lomuto's Comeback

#91

Post by derefr »

mehrdadn wrote: post #76
derefr wrote: post #62

Earlier quoted context omitted.

> unless you have reason to assume your branches are actually close to random. I mean, to the degree that you need to sort the data at all, it contains informational entropy. Many "presents as sorted" data structures trade space for time by keeping track of the internal sortedness of chunks of the data, between sortation passes. Heck, any insert-optimized data structure (B+ trees; LevelDB's sorted-string-tables; N-ar…

I'm struggling to follow your comment. I said real-world data have patterns and aren't completely random, so you can in general expect branch predictors to help (unless, obviously, your data is actually known to be random like in the example). You rebutted with "because load balancers evenly spread their key space, you will frequently find that your inputs can be guaranteed random", as if that somehow contradicts the…

The insight I might have not made clear, is that if you have “this node and its children are already sorted” metadata, then it’s cheaper to check whether a given (fine-grained) input chunk is already sorted—and if so, to directly construct a node from it—than it is to feed it blindly to the sorting algorithm.

If such a pre-check is in play, then the sorting algorithm itself will basically never have the sort of “runs” of sorted values that make some algorithms cheaper. Those “runs” were already plucked out and turned into nodes!

Re: Lomuto's Comeback

#92

Post by tomcam »

klyrs wrote: post #6
cozzyd wrote: post #4

Writing branch-free code (which I find myself sometimes doing to take advantage of simd vectorization) is always really painful. I wonder if someone has made an attempt at better tooling for this.

I tend to use the same method as the author has presented. 1. Write your branchy code 2. Massage the branches until their code is identical (testing frequently) 3. Trim a useless branch, and eat a piece of chocolate

I don’t mind boasting that I’m a world class talent at part 2 of step 3

Re: Lomuto's Comeback

#93

Post by sesuximo »

zbjornson wrote: post #85
sesuximo wrote: post #72

Earlier quoted context omitted.

You mean sorting within a vector register? Can you provide a link or something? I can't find info on this

For one: https://arxiv.org/abs/1704.08579

Thanks. It's kind of sad that there's no single instruction for horizontally sorting in vectors of integers. Horizontal merge/reduce would also be cool

Re: Lomuto's Comeback

#94

Post by a1369209993 »

zombinedev wrote: post #82
a1369209993 wrote: post #71

https://dlang.org/blog/2020/05/14/lomutos-comeback/ gives a 404 error. And archive.org ( http://web.archive.org/cdx/search/cdx?url=https://dlang.org/... ) is also getting nothing but 404s, so it's not a problem on my end. I'm not really sure what's wrong with this site, since other commenters seem not to have noticed a problem.

It's ok now, as far as I can see.

Actually it's it still giving a 404, but (after remembering and looking up the --content-on-error option to wget) it appears TFA is served just fine as if it were a 404 error page.

Re: Lomuto's Comeback

#95

Post by ncmncm »

sesuximo wrote: post #72
ncmncm wrote: post #61

Earlier quoted context omitted.

Indeed, AVX512 instructions can sort 16 int32 or well-behaved float values optimally, with no branches. It is a good final pass to any other algorithm.

You mean sorting within a vector register? Can you provide a link or something? I can't find info on this

The keyword to look for is "sorting network". See, for example, http://cs.brandeis.edu/~hugues/sorting_networks.html.

There is a 28-step 16-input network there. It admits a direct translation to AVX-512 instructions.

What is usually considered minimal differs from what is best for AVX512. AVX512 is happy to do 16 comparisons at each stage; its efficiency is limited only by the number of stages. Thus, a network that did more comparisons in fewer stages would be faster.

Re: Lomuto's Comeback

#96

Post by ComputerGuru »

Ericson2314 wrote: post #78
ComputerGuru wrote: post #49

Earlier quoted context omitted.

Your dismissal of “sorted flat thing” as being necessarily not online is incorrect or unnecessarily strict to your detriment. I wrote this comparing the high-level performance of a “set” (AVL or red-black tree) against just that: Faster lookups, insertions, and in-order traversal than a red-black or AVL tree [0] [0]: https://neosmart.net/blog/2019/sorted-list-vs-binary-search-... (Spoiler: it depends on the nature of…

To be clear I am not against "small sorted flat thing" is an optimization for smaller data structures. My point is I care about the map or set interface. I don't use temporary sets or quicksort to sort....because I don't sort---I don't want a list/array of things in order, basically ever.

Yes, and what I showed you is a set with a set interface, internally implemented as an always-sorted list.

Re: Lomuto's Comeback

#97

Post by ncmncm »

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 should add that Clang is happy to turn c&x|(c-1)&y into cmov.

Re: Lomuto's Comeback

#98

Post by Ericson2314 »

ComputerGuru wrote: post #96
Ericson2314 wrote: post #78

Earlier quoted context omitted.

To be clear I am not against "small sorted flat thing" is an optimization for smaller data structures. My point is I care about the map or set interface. I don't use temporary sets or quicksort to sort....because I don't sort---I don't want a list/array of things in order, basically ever.

Yes, and what I showed you is a set with a set interface, internally implemented as an always-sorted list.

OK sorry, Yes creating a map/set using the small-size optimization is internally doing a sort.

Re: Lomuto's Comeback

#99

Post by ncmncm »

If you define

  inline bool swap_if(
    bool c, long& a, long& b)
  {
    long ta = a, tb = b;
    a = c ? tb : ta;
    b = c ? ta : tb;
    return c;
  }
and then use it in a partition like

   right += swap_if(
     *left
compiled with Clang (which generates `cmov` instructions), the Hoare partition is still faster, and more than twice as fast as `std::sort`.

Using `swap_if` in Lumuto is also faster, but not as much faster. I interpret the difference (vs. array ops) as resulting from reduced L1 bus traffic.

A fully general swap_if,

  template 
  bool swap_if(
    bool c, T& a, T& b)
  {
    T v[2] = { a, b };
    b = v[c], a = v[1-c];
    return c;
  }
could and IMHO should be peephole-optimized to use a pair of `cmov` instructions, but is not in Clang, Gcc, Icc, or MSVC. But even without such an optimization, it makes Quicksort much faster.

(Gcc, incidentally, is very, very sensitive to details of the second swap_if. Change the order of assigning a and b, or use `!c` in place of `1-c`, and it gets much slower, on Intel, for very non-(to me-)obvious reasons. Gcc also will never, ever produce two `cmov` instructions in a basic block. I have filed a bug.)

If `swap_if` were in the Standard Library, it would probably be implemented optimally on all compilers, and almost half of the Standard algorithms could use it to get, often, ~2x performance.

Re: Lomuto's Comeback

#100

Post by [deleted] »

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…

[deleted]
Post reply on HN