1. 19 Jan, 2013 1 commit
  2. 08 Nov, 2012 1 commit
  3. 05 Sep, 2012 1 commit
    • Haruto Otake's avatar
      BITCOUNT: fix segmentation fault. · 749aac72
      Haruto Otake authored
      remove unsafe and unnecessary cast.
      until now, this cast may lead segmentation fault when end > UINT_MAX
      
      setbit foo 0 1
      bitcount  0 4294967295
      => ok
      bitcount  0 4294967296
      => cause segmentation fault.
      
      Note by @antirez: the commit was modified a bit to also change the
      string length type to long, since it's guaranteed to be at max 512 MB in
      size, so we can work with the same type across all the code path.
      
      A regression test was also added.
      749aac72
  4. 18 Jul, 2012 1 commit
    • antirez's avatar
      Don't assume that "char" is signed. · b62bdf1c
      antirez authored
      For the C standard char can be either signed or unsigned, it's up to the
      compiler, but Redis assumed that it was signed in a few places.
      
      The practical effect of this patch is that now Redis 2.6 will run
      correctly in every system where char is unsigned, notably the RaspBerry
      PI and other ARM systems with GCC.
      
      Thanks to Georgi Marinov (@eesn on twitter) that reported the problem
      and allowed me to use his RaspBerry via SSH to trace and fix the issue!
      b62bdf1c
  5. 31 May, 2012 1 commit
    • antirez's avatar
      BITOP bug when called against non existing keys fixed. · 1419406e
      antirez authored
      In the issue #529 an user reported a bug that can be triggered with the
      following code:
      
      flushdb
      set a
      "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
      bitop or x a b
      
      The bug was introduced with the speed optimization in commit 8bbc0768
      that specializes every BITOP operation loop up to the minimum length of
      the input strings.
      
      However the computation of the minimum length contained an error when a
      non existing key was present in the input, after a key that was non zero
      length.
      
      This commit fixes the bug and adds a regression test for it.
      1419406e
  6. 24 May, 2012 7 commits
    • antirez's avatar
      BITOP command 10x speed improvement. · d8668038
      antirez authored
      This commit adds a fast-path to the BITOP that can be used for all the
      bytes from 0 to the minimal length of the string, and if there are
      at max 16 input keys.
      
      Often the intersected bitmaps are roughly the same size, so this
      optimization can provide a 10x speed boost to most real world usages
      of the command.
      
      Bytes are processed four full words at a time, in loops specialized
      for the specific BITOP sub-command, without the need to check for
      length issues with the inputs (since we run this algorithm only as far
      as there is data from all the keys at the same time).
      
      The remaining part of the string is intersected in the usual way using
      the slow but generic algorith.
      
      It is possible to do better than this with inputs that are not roughly
      the same size, sorting the input keys by length, by initializing the
      result string in a smarter way, and noticing that the final part of the
      output string composed of only data from the longest string does not
      need any proecessing since AND, OR and XOR against an empty string does
      not alter the output (zero in the first case, and the original string in
      the other two cases).
      
      More implementations will be implemented later likely, but this should
      be enough to release Redis 2.6-RC4 with bitops merged in.
      
      Note: this commit also adds better testing for BITOP NOT command, that
      is currently the faster and hard to optimize further since it just
      flips the bits of a single input string.
      d8668038
    • antirez's avatar
      BITOP: handle integer encoded objects correctly. · fa4a5d59
      antirez authored
      A bug in the implementation caused BITOP to crash the server if at least
      one one of the source objects was integer encoded.
      
      The new implementation takes an additional array of Redis objects
      pointers and calls getDecodedObject() to get a reference to a string
      encoded object, and then uses decrRefCount() to release the object.
      
      Tests modified to cover the regression and improve coverage.
      fa4a5d59
    • antirez's avatar
      BITCOUNT performance improved. · 7c34643f
      antirez authored
      At Redis's default optimization level the command is now much faster,
      always using a constant-time bit manipualtion technique to count bits
      instead of GCC builtin popcount, and unrolling the loop.
      
      The current implementation performance is 1.5GB/s in a MBA 11" (1.8 Ghz
      i7) compiled with both GCC and clang.
      
      The algorithm used is described here:
      
      http://graphics.stanford.edu/~seander/bithacks.html
      7c34643f
    • antirez's avatar
      bitop.c renamed bitops.c · 80f8028e
      antirez authored
      bitop.c contains the "Bit related string operations" so it seems more
      logical to call it bitops instead of bitop.
      This also makes it matching the name of the test (unit/bitops.tcl).
      80f8028e
    • antirez's avatar
      popcount() optimization for speed. · 343d3bd2
      antirez authored
      We run the array by 32 bit words instead of processing it byte per byte.
      If the code is compiled using GCC __builtin_popcount() builtin function
      is used instead.
      343d3bd2
    • antirez's avatar
      BITCOUNT refactoring. · dbbbe49e
      antirez authored
      The low level popualtion counting function is now separated from the
      BITCOUNT command implementation, so that the low level function can be
      further optimized and eventually used in other contexts if needed.
      dbbbe49e
    • antirez's avatar
      Bit-related string operations moved to bitop.c · 760e7765
      antirez authored
      All the general string operations are implemented in t_string.c, however
      the bit operations, while targeting the string type, are better served
      in a specific file where we have the implementations of the following
      four commands and helper functions:
      
          GETBIT
          SETBIT
          BITOP
          BITCOUNT
      
      In the future this file will probably contain more code related to
      making the BITOP and BITCOUNT operations faster.
      760e7765