24bit integers for ziplists (patch)

[grisha]

This is a small patch to store integers that can fit in 24 bits using 3 bytes which makes ziplists even more memory efficient:

https://github.com/grisha/redis/tree/ziplist_24bit

https://github.com/grisha/redis/commit/2af8ebb25bb64bba385c495457a281b3298391a5

[antirez]

I and Pieter like that... there is a code review effort in progress and it will probably enter 2.6. Thanks! More news soon.

[antirez]

Note to self: if we add this we should make sure to change the RDB version as well for 2.6 / unstable.

[antirez]

Code reviewed, it's broken ;) However it is not ok that the Redis test can't detect such a trivial corruption.
The error is related to how two-complement representation works, when you take the three bytes you are not respecting this representation. I would use shifting of 8 bits to save it at a first glance.

However here the big problem is not that the patch is broken, it's trivial to fix, but that Redis tests were not able to check this trivial corruption. I'm adding a new test that can spot this errors easily.

Cheers,
Salvatore

[antirez]

I just added a test that can spot this issues trivially (unstable branch).

[grisha]

Nice catch, obviously my specific case only used positive integers ;)

There are two ways this can be solved. The simplest is to replace INT24_MIN with 0 and not bother storing two's complements in 24 bits?

The other is some clever bitshifting to preserve that leftmost bit.
Something like: i32 = i32 | ((value & (1 << 31)) >> 7); // (looks ungly - is there a better way?)

[antirez]

@grisha what about this instead?

@@ -299,9 +299,9 @@ static void zipSaveInteger(unsigned char *p, int64_t value, 
         memcpy(p,&i16,sizeof(i16));
         memrev16ifbe(p);
     } else if (encoding == ZIP_INT_24B) {
-        i32 = value;
+        i32 = value<<8;
         memrev32ifbe(&i32);
-        memcpy(p,&i32,sizeof(i32)-sizeof(int8_t));
+        memcpy(p,((unsigned char*)&i32)+1,sizeof(i32)-sizeof(int8_t));
     } else if (encoding == ZIP_INT_32B) {
         i32 = value;
         memcpy(p,&i32,sizeof(i32));
@@ -330,9 +330,9 @@ static int64_t zipLoadInteger(unsigned char *p, unsigned cha
         ret = i32;
     } else if (encoding == ZIP_INT_24B) {
         i32 = 0;
-        memcpy(&i32,p,sizeof(i32)-sizeof(int8_t));
+        memcpy(((unsigned char*)&i32)+1,p,sizeof(i32)-sizeof(int8_t));
         memrev32ifbe(&i32);
-        ret = i32;
+        ret = i32>>8;
     } else if (encoding == ZIP_INT_64B) {

[grisha]

Yes, this is much clearer and works in my tests. I reworked my patch, if that's of any help:

https://github.com/grisha/redis/commit/e3352e49ad9e410dd4e3979476df12738211802b

Thanks!

[antirez]

Thanks, I merged it and tried to go forward along the path of exploiting more bits, given that anyway we are going to update the RDB format.

This is the result, including your patch: https://github.com/antirez/redis/compare/zipenc

Cheers,
Salvatore

[antirez]

Closing :)

[damagao]

       i32 = value;

•    i32 = value<<8;
     memrev32ifbe(&i32);
  

•    memcpy(p,&i32,sizeof(i32)-sizeof(int8_t));
  

•    memcpy(p,((unsigned char*)&i32)+1,sizeof(i32)-sizeof(int8_t));
  

((unsigned char*)&i32)+1 is a bug!!!!

if value is 0x00112233, in memory 33 22 11 00
i32 = value <<8 ; in memory 00 33 22 11
memrev32ifbe(&i32); in memory 11 22 33 00
((unsigned char*)&i32) is addrress value of which is 11