Redis 24bit integers for ziplists (patch)

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

Comment From: 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.

Comment From: antirez

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

Comment From: 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

Comment From: antirez

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

Comment From: 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?)

Comment From: 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) {

Comment From: 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!

Comment From: 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

Comment From: antirez

Closing :)

Comment From: 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