3 ms·
Well, actually, in this case, no, POPCNT is unnecessary here, since you don't actually have to count anything. you only need to know if the bitmask changed whe
by DannyBee 4y ago
Well, actually, in this case, no, POPCNT is unnecessary here, since you don't actually have to count anything. you only need to know if the bitmask changed when you added a new character ;)
But otherwise, yes.
I spent quite a while optimizing GCC's bitmap operations years ago, including implementing some new sparse bitmap types, and the sparse bitmap types i implemented ended up dependent on the speed of popcnt and friends, so yes.
- nebulous1 4y agoit's not sufficient that the newest character in the window is unique? the older characters need to be unique too.
- DannyBee 4y agoI posted how to do it in another comment on the thread.
- rep_lodsb 4y agoInput: "abccdef" Your algorithm will report a match at "bccd" since the "a" wasn't removed from the bitmask.
- DannyBee 4y agoYes, you are correct you would have to xor them back out
- actionfromafar 4y agoI swear I have seen this conversation before. A glitch?
- DannyBee 4y agoNo - he responded on both parts of the thread where i commented. I started to respond here as well, then updated it to redirect to the other comment so we don't end up with two long threads.
- nerpderp82 4y agoIf you XOR them together, you get back to the original conversation.
- nebulous1 4y agoIf you're using OR (unlike the OP) how are you removing the left side of the window? And still, even if the newest character is unique, previous characters might not be
- syrrim 4y agoIn practice if you want the popcount of anything larger than a couple registers you'll want to use vector instructions anyways though. There are a lot of operations that will speed up certain applications if made into their own instruction, not all of them need to be.