7 ms·
Counting the number of matching characters in two ASCII strings
- sm4sh 5y agoWell okay, but guess which one I'd rather have to maintain in a big codebase? Clearly written by a theoretical engineer.
- humblepie 5y agoFor a large codebase, this would be encapsulated and heavily commented, etc. It's something that you pull out when you need to make something "go to eleven" kind of thing.
- raldi 5y agoExactly. You could have some exhaustive unit tests as well, and after that there would be nothing to maintain.
- teachingassist 5y agoPlenty of library functions are already going to be optimised in this type of way - just because they're not visible in your codebase doesn't mean they are not there.
- Forge36 5y agoIt's about use cases. There was an old lady 6 about unoptimized behavior in VB6 and why is wasn't necessary to do so. I had to write a wrapper for it which was optimized in my code. Was it harder to read? Yes. Did it produce a significant performance improvement? Also yes. Software development is about tradeoffs. Demoing one way to improve a simple function helps others trunk how they write code, and more importantly why they wrote specific code
- JKCalhoun 5y agoI've worked with engineers that must read these blogs and try to out-clever everyone. They succeed, and that's the problem.
- deleted 5y ago[deleted]
- commandlinefan 5y ago> rather have to maintain Well, as long as it works, what difference does it make? As long as it's prefixed with a // This compares the matching number of bytes comment, you should never have to mess with it.
- rocqua 5y agoWith a compiler or architecture change, I guess this could create awkward to handle performance regressions.
- rocqua 5y agoSo if your big codebase were profiled, and the 99th percentile case happened to spend 80% of its time in this function, you would still stick to the old function unwaveringly? Even if your system was latency sensitive, and your 99 percentile spikes were far from acceptable? Sure, there are many cases where this is a premature optimization. This blog never said otherwise. But that doesn't mean there is never a time for optimization. And if profiling points at this, then this speedup can be valuable.
- deleted 5y ago[deleted]
- superjan 5y agoI did not know the trick of using memcpy to get the compiler to load a register from an arbitrary char* pointer. Given that the architecture supports it, can you assume it will be optimized like that? I assume this is done to stay away from undefined behavior.
- bombcar 5y agoPoking around godbot seems to indicate ARM and x86 does it, but web assembly doesn't: https://www.godbolt.org/z/r86f9nr1q https://www.godbolt.org/z/r86f9nr1q which I guess makes sense (but web assembly has to become actual code at some point, so maybe the optimization is lost entirely?).
- superjan 5y agoThanks, good idea to share this link in the comments.
- ComputerGuru 5y agoI love Daniel’s optimization posts, but this one seems a little too esoteric: it’s for when autovectorization isn’t fast enough (edit: or isn’t available) but you can’t or don’t want to use SIMD; it gives you a solution solidly better than the former but worse than the latter, and more opaque than either. In all cases, obviously the real magic is in the 64-bit word comparison routine (which doesn’t get more than a passing mention); converting the former problem into the latter is extremely straightforward and obvious - if you know that optimized solutions for the latter exist (I personally didn’t know of this bit twiddling hack (aside from doing it via SIMD, obviously) and am grateful to learn about the approach in Muła’s code).
- bombcar 5y agoIf the optimizing compiler can figure out to use SIMD shouldn’t it also be able to degrade to this when SIMD isn’t available? And if we’re already down the “write it understandable and trust the compiler” path isn’t that the better way to go? It’s interesting to me that C is now effectively a “higher level” language than it may appear on the surface because of optimization by compilers.
- tyingq 5y agoAre there many cases where plain ASCII is okay anymore, anyway? Wouldn't proper UTF-whatever comparisons mandate doing it the slow way, if you wanted counts versus just "same/not the same"?
- bombcar 5y agoThat would be more interesting, something that could handle a UTF-8 string in a similar situation (I guess you'd compare the bytes and then do a walk to see if it was part of a multi-byte character? Maybe the high-bit would help?).
- joawowiij 5y agohex, base64 encoded strings, etc
- 5y ago
- codezero 5y agoCan you do this with an xor and popcount? I suppose that's what the author is implying when they say the compiler takes care of this.
- danbruc 5y agoYou can, the return statement is essentially a popcount. c1 = 0x8080808080808080 c2 = 0x7F7F7F7F7F7F7F7F c3 = 0x0101010101010101 e = ~(x ^ y) return popcount((e & c1) & ((e & c2) + c3)) For those wondering how this works. If two bytes are identical, then the XOR will yield 0x00 and the negation will yield 0xFF. Masking out the seven least significant bits with 0x80 will just yield 0x80 again. Masking out the most significant bit with 0x7F will just yield 0x7F again and adding 0x01 will yield 0x80. Finally combing 0x80 and 0x80 with AND just yields 0x80, i.e. exactly the most significant bit set. On the other hand if two bytes are not identical, then at least one of the two following things happens. The two bytes differ in the most significant bit and therefore the most significant bit of the XNOR is zero. Then masking out the seven least significant bits with 0x80 yields 0x00 and therefore the final AND yields 0x00. Or the two bytes differ in at least one of the seven least significant bits and therefore at least one of the seven least significant bits of the XNOR is zero. Then masking out the most significant bit with 0x7F yields something smaller than 0x7F and adding 0x01 yields something smaller than 0x80, i.e. the most significant bit is zero, and therefore the final AND again yields 0x00 because the first operand is either 0x00 or 0x80. The remaining work is to count the number of set bit, either with popcount or some other construction like the one in the article.
- sfink 5y agoExcept this is suboptimal, as is the code in the original post: it specifies ASCII, so (e & c1) is guaranteed to be zero. In your code, that means you could just do return popcount((e & c2) + c3); (Thanks for writing this out, as otherwise I wouldn't have spotted it.)
- danbruc 5y agoThe author certainly meant extended ASCII and therefore you can not make this change. Sure, it may be technical incorrect but ASCII is so commonly used to refer to extended ASCII that this should probably be the default interpretation unless it is clear from the context, say a discussion of the history of character encodings, that it is meant in its original sense.
- MontagFTB 5y agoI'd still take the traditional solution (https://godbolt.org/z/K5hWqezMP https://godbolt.org/z/K5hWqezMP) over the latter one (https://godbolt.org/z/jaWMM491M https://godbolt.org/z/jaWMM491M). The latter solution requires a traditional check at the tail end of it, so the compiler appears to include the traditional implementation in the latter's solution anyways. Unless this is a significant bottleneck for your application, the latter does not seem practical, and a lot of profiling would have to go into justifying the latter code (which would only be worthwhile if, as I said, this were a significant bottleneck.)
- kens 5y agoIf you like this sort of weird bit operations, you should check out HAKMEM, a huge list of hacks created at MIT in 1972. "Here is some little known data which may be of interest to computer hackers. The items and examples are so sketchy that to decipher them may require more sincerity and curiosity than a non-hacker can muster. Doubtless, little of this is new, but nowadays it's hard to tell." https://w3.pppl.gov/~hammett/work/2009/AIM-239-ocr.pdf https://w3.pppl.gov/~hammett/work/2009/AIM-239-ocr.pdf - see e.g. page 79
- codezero 5y agoI love the curiosity/hacking of the early days of computing, hooking up your registers to an audio amplifier? sure! """ This is a display hack (that is, it makes pretty patterns) with the low 9 bits = Y and the 9 next higher a X; also, it makes interesting, related noises with a stereo amplifier hooked to the X and Y signals. """
- P-ala-din 5y agoI would also recommend Bit Twiddling Hacks By Sean Eron Anderson [1] and Hacker's Delight. [1] - https://graphics.stanford.edu/~seander/bithacks.html https://graphics.stanford.edu/~seander/bithacks.html
- f00zz 5y agoCool trick, but if I'm reading this correctly the test fails for characters with codes larger than 127
- johnghanks 5y agoOriginal Title: How to use weird hacks to make your code unreadable.
- KETpXDDzR 5y agoWhere are the benchmarks?
- b20000 5y agobut the real question is, can you write the most optimal version on the spot in under a minute, while your interviewer is babbling and distracting you, and use a binary search?
- draw_down 5y agoHmm, I kinda liked the original code.
- GianFabien 5y agoIsn't this another example of relying on a "sufficiently smart compiler" ?