4 ms·

SMART (fastest substring search algorithms) https://smart-tool.github.io/smart/ https://smart-tool.github.io/smart/ is up for several years. EPSM, by S. Faro an

by rurban 5y ago

SMART (fastest substring search algorithms) https://smart-tool.github.io/smart/ https://smart-tool.github.io/smart/ is up for several years. EPSM, by S. Faro and O. M. Kulekci still the fastest known strstr method, and they still come up with their own. .NET turning more and more into Linux.

oaiey 5y ago
I am not deep into the topic. Is that maybe because of a SIMD variant is possible in one algorithm and not the other. .NET is doing a lot of processor specific optimization right now and getting from that it's current speed. On pure paper approach, SIMD is not a thing but on processors it is. Just waking up. Maybe I am completely off.
- charcircuit 5y ago
  That project includes implementations which use simd. I don't know if those are the fastest or how it compares to this proposed one.
tester34 5y ago
What does algorithm (approach) has to SIMD / Hardware intrinsics?
- tsimionescu 5y ago
  Some algorithms are amenable to SIMD, others are not. To utilize SIMD, you need the same set of operations on big chunks of data stored one next to to the other in memory. This fits for example with algorithms which use arrays to store data, and doesn't work at all for alogrithms which rely on linked lists.
Someone 5y ago
Various links on that page (e.g. https://www.dmi.unict.it/~faro/smart/howto.php https://www.dmi.unict.it/~faro/smart/howto.php) are dead for me, and browsing the source isn’t easy because they release .zip/.tar.gz. files (https://github.com/smart-tool/smart/releases https://github.com/smart-tool/smart/releases), so I didn’t make that effort, but theoretical algorithms often count character or byte comparisons, not nanoseconds. For the latter, code size and cache-friendliness matter, and the best code almost always must be tuned for one specific CPU, nowadays one specific state of a CPU (do you assume the SIMD hardware is powered up? If it isn’t, is using SIMD for short strings worth it?) There probably also is a choice to be made as to what cases to optimize most for: length of search string, length of to-be-searched for string, case-sensitivity, diacritics-sensitivity, distribution of results (if, most of the time, the string is found close to the start, decreasing algorithm set up time at the cost of some speed may be worth it). ¿Are there corner cases where locale matters?
- orf 5y ago
  You can of course browse the source on GitHub: https://github.com/smart-tool/smart/tree/master/source https://github.com/smart-tool/smart/tree/master/source The tarballs are just a feature of GitHub, not something they specifically release.
  - Someone 5y ago
    But they chose to point to them and not to the source. That made me think that’s how they intend to release the code.
    - rurban 5y ago
      Their site broke recently. Before it had nice benchmarks included. Apparently string backend researchers are not that good in maintaining website frontends.
    - orf 5y ago
      Certainly, but I don’t think it’s unreasonable of them to assume a prior basic knowledge of GitHub. The releases page is the prebuilt binaries they publish, and there are several links you can click to view the source at the tag, commit or main-branch level.
- Const-me 5y ago
  > the best code almost always must be tuned for one specific CPU There’re very few relevant differences between CPUs of the same instruction set. The author of that PR implemented fast paths for SSE2, AVX2, and NEON. Combined, they cover like 90% of CPUs; the only notable missing one is the 32-bit ARMv7, C# doesn’t support vector intrinsics for that architecture. > do you assume the SIMD hardware is powered up? Modern AMD64 CPUs never power off just the SIMD. For AMD64 ISA, SSE1 and SSE2 are included in the base instruction set. Modern C++ compilers compile FP32 and FP64 math into SSE1 and SSE2 respectively, e.g. double y=x*3.0 compiles into MULSD instruction from SSE2 SIMD subset. Powering down that hardware would be too expensive for many programs. Some early Intel’s AVX CPUs, like Sandy Bridge from 2011, powered down half of their SIMD hardware. On these CPUs, first time a program uses AVX instructions which process 32-byte vectors, the instructions run at half the throughput and +1 cycle of latency. The performance penalty lasts until the state transition is complete, like ~100 nanoseconds or something. AFAIK, for 32-byte AVX vectors, that got fixed years ago in the newer processors.
pjmlp 5y ago
Having a search algorithm implemented in C has nothing to do with Linux.

by rurban 5y ago

oaiey 5y ago

I am not deep into the topic. Is that maybe because of a SIMD variant is possible in one algorithm and not the other. .NET is doing a lot of processor specific optimization right now and getting from that it's current speed. On pure paper approach, SIMD is not a thing but on processors it is. Just waking up. Maybe I am completely off.

charcircuit 5y ago
That project includes implementations which use simd. I don't know if those are the fastest or how it compares to this proposed one.

tester34 5y ago

What does algorithm (approach) has to SIMD / Hardware intrinsics?

tsimionescu 5y ago
Some algorithms are amenable to SIMD, others are not. To utilize SIMD, you need the same set of operations on big chunks of data stored one next to to the other in memory. This fits for example with algorithms which use arrays to store data, and doesn't work at all for alogrithms which rely on linked lists.

Someone 5y ago

Various links on that page (e.g. https://www.dmi.unict.it/~faro/smart/howto.php https://www.dmi.unict.it/~faro/smart/howto.php) are dead for me, and browsing the source isn’t easy because they release .zip/.tar.gz. files (https://github.com/smart-tool/smart/releases https://github.com/smart-tool/smart/releases), so I didn’t make that effort, but theoretical algorithms often count character or byte comparisons, not nanoseconds. For the latter, code size and cache-friendliness matter, and the best code almost always must be tuned for one specific CPU, nowadays one specific state of a CPU (do you assume the SIMD hardware is powered up? If it isn’t, is using SIMD for short strings worth it?) There probably also is a choice to be made as to what cases to optimize most for: length of search string, length of to-be-searched for string, case-sensitivity, diacritics-sensitivity, distribution of results (if, most of the time, the string is found close to the start, decreasing algorithm set up time at the cost of some speed may be worth it). ¿Are there corner cases where locale matters?

orf 5y ago
You can of course browse the source on GitHub: https://github.com/smart-tool/smart/tree/master/source https://github.com/smart-tool/smart/tree/master/source The tarballs are just a feature of GitHub, not something they specifically release.
- Someone 5y ago
  But they chose to point to them and not to the source. That made me think that’s how they intend to release the code.
  - rurban 5y ago
    Their site broke recently. Before it had nice benchmarks included. Apparently string backend researchers are not that good in maintaining website frontends.
  - orf 5y ago
    Certainly, but I don’t think it’s unreasonable of them to assume a prior basic knowledge of GitHub. The releases page is the prebuilt binaries they publish, and there are several links you can click to view the source at the tag, commit or main-branch level.
Const-me 5y ago
> the best code almost always must be tuned for one specific CPU There’re very few relevant differences between CPUs of the same instruction set. The author of that PR implemented fast paths for SSE2, AVX2, and NEON. Combined, they cover like 90% of CPUs; the only notable missing one is the 32-bit ARMv7, C# doesn’t support vector intrinsics for that architecture. > do you assume the SIMD hardware is powered up? Modern AMD64 CPUs never power off just the SIMD. For AMD64 ISA, SSE1 and SSE2 are included in the base instruction set. Modern C++ compilers compile FP32 and FP64 math into SSE1 and SSE2 respectively, e.g. double y=x*3.0 compiles into MULSD instruction from SSE2 SIMD subset. Powering down that hardware would be too expensive for many programs. Some early Intel’s AVX CPUs, like Sandy Bridge from 2011, powered down half of their SIMD hardware. On these CPUs, first time a program uses AVX instructions which process 32-byte vectors, the instructions run at half the throughput and +1 cycle of latency. The performance penalty lasts until the state transition is complete, like ~100 nanoseconds or something. AFAIK, for 32-byte AVX vectors, that got fixed years ago in the newer processors.

pjmlp 5y ago

Having a search algorithm implemented in C has nothing to do with Linux.