Packing a string of digits into an integer quickly

https://lemire.me/blog/2023/07/07/packing-a-string-of-digits-into-an-integer-quickly/

by mfiguiere • 3 years ago

93 18 3 years ago

gumby• 3 years ago

I don't understand how this can work: there are 15 (or 7 :-) other characters with the same bottom four bits as each digit. How does it distinguish between, say, '4' and 't'? Space and '0' have the same lower four bits: \0!

jcparkyn• 3 years ago

I think the author is only concerned with decimal digits (0-9).

patrec2• 3 years ago

No, he says that the strings can contain spaces and other characters but that he wants them ordered (only) by the decimal digits in them. I don't see how this can work either.

n2d4• 3 years ago

It doesn't distinguish, the non-digit character index is hardcoded into the bitmask (note the missing f in the second hex literal):

  part1 = _pext_u64(part1, 0x0f0f0f0f0f0f0f0f);
  part2 = _pext_u64(part2, 0x0f000f0f0f0f0f0f);

You are right that if you were to use a space in an unexpected position, the code wouldn't work.

hammock• 3 years ago

Can’t you just search through and remove all the non-digit characters? (Excel user here)

recursive• 3 years ago

You can. But the point of this exercise seems to be cpu efficiency.

heywhatupboys• 3 years ago

yea and you could print the number, mail it to your friend, ask him to call you back and type in the number on his phone. Then have a recording tool listen in on his key presses, and write them to a file.

The time scale between OP's code and yours is about the same as the timescale between yours and mine :)

efitz• 3 years ago

It was a fairly common thing to do very similar operations on Apple ][ computers.

6502 had a BCD (binary coded decimal) mode; basically when in BCD mode arithmetic operators carried at 0x9 rather than 0xF, and operations worked nibble-wise rather than byte-wise. So it was common to represent 2 digits in one bye regardless of hex vs decimal.

I actually have been thinking about this lately because of the other half of the problem, ie ASCII <—> native types. On the Apple 2 one really cool speed trick was to store strings directly on the screen. The Apple 2 text screen was memory mapped (0x400 - 0x7FF IIRC). To write strings to the screen in assembly, you wrote the ASCII character codes to the right memory locations. But if you were trying to eke out every single cycle you could, and your strings were fixed length, you didn’t need to store them somewhere and copy them to the screen; you could use the screen as the store for your strings.

I once made a stupid program that counted to one million this way; it ran fast enough to watch it finish.

wahahah• 3 years ago

Huh, that decimal representation is a pretty attractive idea, I wonder why I haven't heard of it before or seen it in use at all.

100/256 seems very tolerable efficiency-wise.

dcsommer• 3 years ago

The BEAM VM (Erlang/Elixir) recently optimized a related procedure as well https://github.com/erlang/otp/pull/7426

anonymousDan• 3 years ago

Anyone know an efficient way of zipping/interleaving two bitmasks on Intel? Assume both bitmasks are in their own mask registers, and the top halves and bottom halves can be zipped into separate output registers. My current solution uses the pdep instruction.

m1el• 3 years ago

https://gist.github.com/m1el/e16fc153076d5764c95835de2936afe...

Here's my solution, which also uses pdep/pext

DeathArrow• 3 years ago

How often these days strings are arrays of characters terminated with '\0' instead of UTF16?

sagarm• 3 years ago

I think only Java and JavaScript use UTF-16? Every C/C++ system I've worked on uses UTF-8, and that's where you'd have access to these intrinsics.

Packing a string of digits into an integer quickly

Related Stories