wmu

I found TDD unpractical. Can recall one situation when used TDD. I was writing a printf-like formatter in C++ and prepared a lot of tests cases in advance. That approach worked well at early state of development. however, further development had revealed quirks I hadn't predicted. As a result, the number and complexity of tests got increased.

My typical practice is to work out an API, write early scratches of implementation and test only simple cases. Then I can inspect two things: how the API works in real code and what else should be tested. In other words tests help to establish an API, then to stabilize the implementation.

Speaking of benchmarking against older CPUs: the paper falls into the "short communication" category, we didn't want to discuss all possible hardware configurations.

For instance our SSE/AVX2 algorithms have been included in a great, mature library written and maintained by Alfred Klomp: https://github.com/aklomp/base64 (the library includes also vectorized code for ARM CPUs).

A few years ago I wrote an accounting software using that approach. The C++ code was calling predefined set of stored procedures and most logic (especially constraints) was in db. Fixing bugs not related to GUI was easy and, in most cases, not visible to end users. We also had a request to let an external software to insert some data into certain tables. I just created the procedure for this particular case and guys from another company just integrated their software without any problems.

The hand-coded AVX2 procedure is far from optimal form, they waste time on horizontal addition in each iteration.

The First Rule of SIMD-ization says: keep all the intermediate results in vector(s), do horizontal reduction at the end.

Conversion from comparison result into vector of integers can be done a bit simpler: just one bit-and is needed and then cast to __m256i (casting doesn't emit any code as SIMD registers are untyped).

That's really nice, I enjoyed reading the code.

I do not use any dedicated IDE, I use my system (Linux) as an IDE: vim for editing, multiple terminal windows for various tasks (compilation, debugging, running grep, find, sed). This is merely a practical choice, backed by experience in various environments.

When I was using DOS, which does not have any of these facilities, then an IDE was indeed a great choice.

BTW, does anybody know a paper about doing some DB ops directly on disc controllers? The other day my former colleague mentioned that he come across such paper (maybe a blog post?), but we couldn't find it. It's really interesting idea and I believe it's doable, although under very specific circumstances (disc vendor specific, sectors layout aligned to DB needs, etc.).

> GYB, Generate Your Boilerplate

Love the name :)

I did similar thing, but the output are unix man pages: https://github.com/WojciechMula/man-intrinsics

"A naive Python script that loops over all needles and calls str.find in a loop to find all matches. This is not Aho–Corasick [...]".

I'm the author of pyahocrasick, a python C extension that implements the AC. I'd love to see it in the comparison. :)

That's a super-cool list! Some points are generic, some very NASA-centric. Nonetheless, all worth to read.

To wheat your appetite: "One must pay attention to workaholics. If they get going in the wrong direction, they can do a lot of damage in a short time."; or "Abbreviations are getting to be a pain. [...] Use them sparingly in presentations unless your objective is to confuse."; "The project manager who is the smartest man on his project has done a lousy job of recruitment."

Intel also had KNC instruction set (AVX512-like) on Xeon Phi (these CPUs available on PCI cards). They abandoned it in favour of good old x86. One of important factors was the difficulties related to tooling, especially necessity of cross-compilation.

Sorry for a non-constructive comment, just wanted to say your paper is great. :)

Well, there is also no AVX512 mentioned.

The code is not optimal, because there are implicit conversions to int (32-bit values) which are quite expansive. There should be explicit casts to uint16_t, like this: dest.r = uint16_t(uint16_t(dest.r * invAlpha) + uint16_t(c.r * c.a)) >> 8;

Recently I checked how different compilers vectorize various C++ standard algorithms: http://0x80.pl/notesen/2019-02-02-autovectorization-gcc-clan...

You'll also find there a hint how to rewrite std::replace algorithm to make it vectorizable.

This is not the same. For sequence [5,5,4,3,3,2,1,1] "sort -u" returns [1,2,3,4,5], while "sort | uniq -u" returns [2,4].

Easier would be just use 'cat list_of_numbers | sort | uniq -u' to get the unique entries.

I'd love to see also comparison with B-trees (https://code.google.com/archive/p/cpp-btree/). In my tests done a few years ago this implementation was faster than std::map. And my guess is the reason of it is better use of cache.

There was an article on HN, where the author stated that they didn't like to write own algorithms "like in '90".

In this context, the Arseny's article should be titled: "How to be old-school and tailor algorithms & data structures to your needs". I have this haunting feeling that people nowadays are afraid of "reinventing wheel" even though it'd pay off. A recurring argument is that the standard library or boost or something available on github is better than a custom solution. But as we see, there are cases where saying "nope, I'll do better job myself" has sense.

Great! :) My initial comment wasn't clear, sorry for that.

I'm saying that map.contains(x) == bool(map.count(x))

std::unordered_map has method count(), C++20 will be probably just a wrapper for the method.

https://en.cppreference.com/w/cpp/container/unordered_map/co...

Perhaps nobody would see this, as the thread is already dead, but... :) I managed to include description of your algorithm and updated results, including procedures by aqrit: http://0x80.pl/notesen/2019-01-05-avx512vbmi-remove-spaces.h...

BTW: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88798

Thanks a lot for such a great explanation!

You might have seen vcompessd in context of sorting; I used it for partition part in qsort.

Thank you again! Take a look: https://github.com/WojciechMula/toys/tree/master/avx512-remo...

Your AVX2 is better in benchmarks than Zach's AVX512VBMI, wow. I have to admit that looked at the code but got lost. :) Will need more time to digest it.

However, in despacing English texts and CSV, Zach's variant is still faster.

Thank you! :)

Your approach is incredibly fast. I love the code, it's so short. :)

Please take look at https://github.com/WojciechMula/toys/tree/master/avx512-remo..., I put there some raw numbers; will update the article later.

For English texts your algorithm is more than 20 times faster (twenty, not a typo), for CSVs the speed-up is "only" 9. However, I'd love to compare it with a well tuned scalar code.

One important take away for me is that I underestimated pext; it's a powerful instruction. (on AMDs terribly slow, though)