Optimize integer zset scores in listpack (converting to string and back)#10486
Optimize integer zset scores in listpack (converting to string and back)#10486oranagra merged 9 commits intoredis:unstablefrom oranagra:zset_listpack_int
Conversation
| double min = -4503599627370495; /* (2^52)-1 */ | ||
| double max = 4503599627370496; /* -(2^52) */ |
There was a problem hiding this comment.
I think the comments for min and max are swapped.
There was a problem hiding this comment.
the comments are wrong, but i'm also uncertain the values are correct.
in integer's 2's complement, the negative side is the larger one (unlike this code).
however, doubles have a distinct sign bit, so i think their range to the positive and negative is the same.
i think the numbers should be 4503599627370495 and -4503599627370495
but i also think this check doesn't necessarily have to be here, and can't cause much harm.
i.e. i suppose we can also safely keep a value of 4503599627370495*4 as long without precision loss (but not *3).
and also, even if the range check would have been too big (allowing some values that can't be stored in long), the later conversion check is what actually decides, so this range check is just an optimization to avoid casting overheads?
There was a problem hiding this comment.
see my last commit and the updated top comment.
There was a problem hiding this comment.
The same changes need to be made for https://github.com/redis/redis/blob/b8eb2a73408fa3b8845760857dd6fcccb62107fe/src/rdb.c#L601:L602
Since doubles have distict sign bit, the range should be +/- ((2^52)-1) inclusive. Note that this is just a speedup to avoid the casting check, which is what actually matters.
Co-authored-by: Viktor Söderqvist <[email protected]>
|
Using the following test code shows that performance is indeed improved. Here are a few test optimizations to avoid additional performance consumption
Test codes long long start = ustime();
for (int j = 0; j < 1000000; j++) {
unsigned char *lp = lpNew(2183);
for (long long i = 4503599627370494; i > 4503599627370494 - 128; i--) {
sds ele = sdscatfmt(sdsempty(), "key%I", i);
lp = zzlInsert(lp, ele, i);
sdsfree(ele);
}
zfree(lp);
}
printf("consume: %lld \n", ustime() - start); |
When we have a double score and we know we cannot convert it to an integer, we convert it to a string, but then listpack was again trying to convert that string to an integer. Now we have an lpInsertDouble API that avoids these overheads. Note: i'm not happy with the result, specifically the interface of lpInsert (i.e. the NOT_INT part) Unrelated: improve lpStringToInt64 not to try converting long strings to integers.
|
i pushed a commit that avoids the extra string to integer conversion attempt, didn't try to benchmark it yet. p.s. the right solution to all of that is probably to add native double encoding for listpack (i.e. save the actual double bits), but that's complicated, and i'm not certain we have spare bits in the header to denote that type. |
|
benchmark using the code from #10486 (comment)
this is expected since the last commit attempts to resolve issues from when fractional parts are used, but for some reason when i try to measure the same with fractional numbers, i don't see any difference between the 3 options. |
|
|
so maybe i should revert my last commit. |
|
@oranagra Perhaps we can reserve |
|
i don't see a point in reserving the API if we don't have the code to back it. we can add that later again if needed. |
|
I made an attempt to store double in listpack, it's really complicated, not in the storage, but in the interface of listpack (lpGet, lpGetValue, lpFind) will be changed dramatically, and eventually the caller (hash, zsortset, list, stream) will need to handle double encoding(a lot of changes), but it only improves zsortset. |
|
Good job @sundb. So I guess the conclusion is that it's not worth it, storing IEEE doubles in listpack. Maybe we can optimize double <---> string conversion instead? There are some libraries that are several times faster than snprinf and strtod. For snprintf, there's the Grisu2 and Grisu3 algorithms. Paper: https://www.cs.tufts.edu/~nr/cs257/archive/florian-loitsch/printf.pdf, implementation (C++, 3-clause BSD): https://github.com/google/double-conversion. I haven't found a plain C implementation yet. For strtod, there's https://github.com/fastfloat/fast_float and https://github.com/lemire/fast_double_parser and blog posts like https://lemire.me/blog/2020/03/10/fast-float-parsing-in-practice/. Daniel Lemire has a lot of papers and blog posts on these topics. |
|
@zuiderkwast You remind me of #8825 |
@zuiderkwast WRT to #8825 I've opened a PR that uses a plain C implementation of grisu2. (tests are still failing and I need to address it but it would be of interest to have your opinion on it ). PR link: #10587 |
|
@yossigo please review (see updated top comment). i'd like to merge this. |
| * i.e. all double values in that range are representable as a long without precision loss, | ||
| * but not all long values in that range can be represented as a double. | ||
| * we only care about the first part here. */ | ||
| if (d < -LLONG_MAX/2 || d > LLONG_MAX/2) |
There was a problem hiding this comment.
there is a warning, https://github.com/redis/redis/runs/6057010293?check_suite_focus=true#step:4:139
PR link: #10595
util.c:574:42: error: implicit conversion from 'long long' to 'double' changes value from 4611686018427387903 to 4611686018427387904 [-Werror,-Wimplicit-const-int-float-conversion]
if (d < -LLONG_MAX/2 || d > LLONG_MAX/2)
There is a implicit conversion warning in clang:
```
util.c:574:23: error: implicit conversion from 'long long' to 'double'
changes value from -4611686018427387903 to -4611686018427387904
[-Werror,-Wimplicit-const-int-float-conversion]
if (d < -LLONG_MAX/2 || d > LLONG_MAX/2)
```
introduced in redis#10486
Co-authored-by: sundb <[email protected]>
There is a implicit conversion warning in clang:
```
util.c:574:23: error: implicit conversion from 'long long' to 'double'
changes value from -4611686018427387903 to -4611686018427387904
[-Werror,-Wimplicit-const-int-float-conversion]
if (d < -LLONG_MAX/2 || d > LLONG_MAX/2)
```
introduced in #10486
Co-authored-by: sundb <[email protected]>
…ck) (redis#10486) When the score doesn't have fractional part, and can be stored as an integer, we use the integer capabilities of listpack to store it, rather than convert it to string. This already existed before this PR (lpInsert dose that conversion implicitly). But to do that, we would have first converted the score from double to string (calling `d2string`), then pass the string to `lpAppend` which identified it as being an integer and convert it back to an int. Now, instead of converting it to a string, we store it using lpAppendInteger`. Unrelated: --- * Fix the double2ll range check (negative and positive ranges, and also the comparison operands were slightly off. but also, the range could be made much larger, see comment). * Unify the double to string conversion code in rdb.c with the one in util.c * Small optimization in lpStringToInt64, don't attempt to convert strings that are obviously too long. Benchmark; --- Up to 20% improvement in certain tight loops doing zzlInsert with large integers. (if listpack is pre-allocated to avoid realloc, and insertion is sorted from largest to smaller)
There is a implicit conversion warning in clang:
```
util.c:574:23: error: implicit conversion from 'long long' to 'double'
changes value from -4611686018427387903 to -4611686018427387904
[-Werror,-Wimplicit-const-int-float-conversion]
if (d < -LLONG_MAX/2 || d > LLONG_MAX/2)
```
introduced in redis#10486
Co-authored-by: sundb <[email protected]>
When the score doesn't have fractional part, and can be stored as an integer,
we use the integer capabilities of listpack to store it, rather than convert it to string.
This already existed before this PR (lpInsert dose that conversion implicitly).
But to do that, we would have first converted the score from double to string (calling
d2string),then pass the string to
lpAppendwhich identified it as being an integer and convert it back to an int.Now, instead of converting it to a string, we store it using lpAppendInteger`.
Unrelated:
were slightly off. but also, the range could be made much larger, see comment).
Benchmark;
Up to 20% improvement in certain tight loops doing zzlInsert with large integers.
(if listpack is pre-allocated to avoid realloc, and insertion is sorted from largest to smaller)