Consolidate all uses of the fast range mapping technique in util/fastrange.h #23994

sipa commented at 4:55 PM on January 6, 2022: member

Several places in the codebase use the fast range mapping technique described in https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/, some for 32-bit ranges, some for 64-bit ones.

Move all of these to util/fastrange.h, and give them a consistent name.

[moveonly] Move MapIntoRange() to separate util/fastrange.h c6d15c45d9

scripted-diff: rename MapIntoRange to FastRange64

-BEGIN VERIFY SCRIPT-
sed -i -e 's/MapIntoRange/FastRange64/' src/blockfilter.cpp src/test/fuzz/golomb_rice.cpp src/util/fastrange.h
-END VERIFY SCRIPT-

96ecd6fa3e

DrahtBot added the label Build system on Jan 6, 2022

DrahtBot added the label Utils/log/libs on Jan 6, 2022

Sjors approved

Sjors commented at 11:07 AM on January 7, 2022: member

ACK b6e8ebc361682ba90cfcdd3af0fd39da85d1ca2a

nit: funcion -> function in last commit message

in src/util/fastrange.h:14 in b6e8ebc361 outdated

   9 | +
  10 | +// See: https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
  11 | +
  12 | +/** Map a value x that is uniformly distributed in the range [0, 2^64) to a
  13 | + *  value uniformly distributed in [0, n) by returning the upper 64 bits of
  14 | + * x * n. */

shaavan commented at 3:04 PM on January 7, 2022:

A minor nit. Feel free to ignore.

How about putting the reference link after the explanation?

/** Map a value x that is uniformly distributed in the range [0, 2^64) to a
 *  value uniformly distributed in [0, n) by returning the upper 64 bits of
 * x * n. */
 
 // See: https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/

As this convention is followed throughout the codebase and seems more logical.

sipa commented at 3:10 PM on January 7, 2022:

That's not a valid doxygen comment.

I factored out the URL above, because it's more a comment for the entire file, than just that individual function.

sipa commented at 6:37 PM on January 7, 2022:

I've rewritten the comments in the last commit.

shaavan approved

shaavan commented at 3:09 PM on January 7, 2022: contributor

ACK b6e8ebc361682ba90cfcdd3af0fd39da85d1ca2a

This PR:

Renames MapIntoRange -> FastRange64. Moves it to util/fastrange.
Renames FastMod -> FastRange32. Moves it to util/fastrange.
Uses FastRange32 consistently throughout the codebase.

I like the refactoring as this makes the functions more consistent in their naming scheme and where they are defined. I checked these functions are being appropriately used wherever possible.

I had one suggestion, though.

sipa force-pushed on Jan 7, 2022

Add FastRange32 function and use it throughout the codebase efab28b06b

sipa force-pushed on Jan 7, 2022

Sjors commented at 7:19 PM on January 7, 2022: member

ACK efab28b06bfaa50c41337e84136cb58437e7ba00

shaavan approved

shaavan commented at 11:15 AM on January 8, 2022: contributor

reACK efab28b06bfaa50c41337e84136cb58437e7ba00

Changes since my last review:

Rewritten documentation in util/fastrange.h.
Reordered function definition in util/fastrange.h.

The new documentation looks a lot better. It’s able to remain concise while also clearly explaining the following code. Also, now the placement of links is a lot more meaningful.

I prefer the new ordering of functions as it feels more logical, and also it follows lexicographic ordering, so that is a plus. FastRange32 followed by FastRange64.

DrahtBot commented at 6:58 AM on January 10, 2022: member

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#23810 (refactor: destroy all C-style casts; use modern C++ casts, enforce via -Wold-style-cast by PastaPastaPasta)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

MarcoFalke removed the label Build system on Jan 10, 2022

MarcoFalke added the label Refactoring on Jan 10, 2022

MarcoFalke approved

MarcoFalke commented at 9:53 AM on January 10, 2022: member

review ACK efab28b06bfaa50c41337e84136cb58437e7ba00 🍸

<details><summary>Show signature</summary>

Signature:

</details>

MarcoFalke merged this on Jan 10, 2022

MarcoFalke closed this on Jan 10, 2022

sidhujag referenced this in commit a3cd5163eb on Jan 10, 2022

DrahtBot locked this on Jan 10, 2023