4 ms·

This is such a mashup of conflicting advice. Don’t optimize! Use SIMD! If you’re reading from disk you’re I/O bound! I am embarrassed for the ACM.

hhmc 6y ago
It’s also strange to advocate for using a stdlib provided sort. It’s hard to imagine a stdlib worth it’s salt that provides ‘sort’ but not some kind of ‘linear search’ (and the stdlib implementation would likely use SIMD).
- Joker_vD 6y ago
  Well, Go's standard library has no linear search routine. But it does have both sort and binary search.
- gameswithgo 6y ago
  standard libraries are only just now starting to use SIMD at all. .NET has been working hard on SIMDifying their core libraries lately. Do any C++ implementations of the std do so? Or do they just lean on llvm/gcc to autovectorize when possible?
  - formerly_proven 6y ago
    There's really no point providing a hand-rolled SIMD implementation for stuff like std::max_element. It's a very trivial loop that any compiler can and will vectorize. Auto-vectorization in general "just works" for basic stuff. It's only the complex stuff where you can really benefit from hand-rolled SIMD implementations; you'll know it when you see it.
kevinventullo 6y ago
It doesn’t inspire much confidence in a candidate’s ability to write software of even moderate complexity if their reasoning for using sort instead of a 5-liner was that their 5-liner could contain bugs.
- benrbray 6y ago
  Writing software of moderate complexity requires delegation. One big way to save dev+testing+debug time is to rely on specialized libraries whose priority is to be fast+correct. If profiling later reveals that sort() is the bottleneck, by all means, optimize away.
- ben-schaaf 6y ago
  Even worse when you consider most languages have a built-in way to do linear search too, so really it's just turning a fast 1 liner into a more complex slower 1 liner.
- JackFr 6y ago
  I sometimes ask "In the language of your choice write a function to find the maximum of a list of integers" as an interview question. I often have to typically follow it by "Really, there's no subtle trick, just find the max...". The number of people who use a 'sort' and take the first element is definitely non-zero. It's also astonishing the number of buggy implementations there are. (Well in fairness there is one buggy implementation which everyone who gets it wrong typically makes -- initially setting the max to 0) I'm not sure if this is an argument for or against coding exercises in interviews -- it was just a surprising experience for me.
  - CyberDildonics 6y ago
    You have never had anyone initialize the max to MIN_INTEGER or something like that? I have made similar mistakes, but I've had to write these functions before, so I know better.
    - lixtra 6y ago
      I couldn’t remember such a thing as MIN_INTEGER and what if someone changes the data type? Why not assume the first element is the max and start your search from the second. Ah, dam. Now you have to check that your vector has at least one element. It ain’t easy.
deleted 6y ago
[deleted]

hhmc 6y ago

It’s also strange to advocate for using a stdlib provided sort. It’s hard to imagine a stdlib worth it’s salt that provides ‘sort’ but not some kind of ‘linear search’ (and the stdlib implementation would likely use SIMD).

Joker_vD 6y ago
Well, Go's standard library has no linear search routine. But it does have both sort and binary search.
gameswithgo 6y ago
standard libraries are only just now starting to use SIMD at all. .NET has been working hard on SIMDifying their core libraries lately. Do any C++ implementations of the std do so? Or do they just lean on llvm/gcc to autovectorize when possible?
- formerly_proven 6y ago
  There's really no point providing a hand-rolled SIMD implementation for stuff like std::max_element. It's a very trivial loop that any compiler can and will vectorize. Auto-vectorization in general "just works" for basic stuff. It's only the complex stuff where you can really benefit from hand-rolled SIMD implementations; you'll know it when you see it.

kevinventullo 6y ago

It doesn’t inspire much confidence in a candidate’s ability to write software of even moderate complexity if their reasoning for using sort instead of a 5-liner was that their 5-liner could contain bugs.

benrbray 6y ago
Writing software of moderate complexity requires delegation. One big way to save dev+testing+debug time is to rely on specialized libraries whose priority is to be fast+correct. If profiling later reveals that sort() is the bottleneck, by all means, optimize away.
ben-schaaf 6y ago
Even worse when you consider most languages have a built-in way to do linear search too, so really it's just turning a fast 1 liner into a more complex slower 1 liner.
JackFr 6y ago
I sometimes ask "In the language of your choice write a function to find the maximum of a list of integers" as an interview question. I often have to typically follow it by "Really, there's no subtle trick, just find the max...". The number of people who use a 'sort' and take the first element is definitely non-zero. It's also astonishing the number of buggy implementations there are. (Well in fairness there is one buggy implementation which everyone who gets it wrong typically makes -- initially setting the max to 0) I'm not sure if this is an argument for or against coding exercises in interviews -- it was just a surprising experience for me.
- CyberDildonics 6y ago
  You have never had anyone initialize the max to MIN_INTEGER or something like that? I have made similar mistakes, but I've had to write these functions before, so I know better.
  - lixtra 6y ago
    I couldn’t remember such a thing as MIN_INTEGER and what if someone changes the data type? Why not assume the first element is the max and start your search from the second. Ah, dam. Now you have to check that your vector has at least one element. It ain’t easy.

deleted 6y ago

[deleted]