• antirez's avatar
    BITOP command 10x speed improvement. · 8bbc0768
    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.
    8bbc0768
bitops.c 13.3 KB