- 24 May, 2012 13 commits
-
-
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.
-
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.
-
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
-
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).
-
antirez authored
Fuzzing tests of BITCOUNT / BITOP are iterated multiple times. The new BITCOUNT fuzzing test uses random strings in a wider interval of lengths including zero-len strings.
-
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.
-
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.
-
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.
-
antirez authored
The Redis implementation is tested against Tcl implementations of the same operation. Both fuzzing and testing of specific aspects of the commands behavior are performed.
-
antirez authored
The motivation for this new commands is to be search in the usage of Redis for real time statistics. See the article "Fast real time metrics using Redis". http://blog.getspool.com/2011/11/29/fast-easy-realtime-metrics-using-redis-bitmaps/ In general Redis strings when used as bitmaps using the SETBIT/GETBIT command provide a very space-efficient and fast way to store statistics. For instance in a web application with users, every user can be associated with a key that shows every day in which the user visited the web service. This information can be really valuable to extract user behaviour information. With Redis bitmaps doing this is very simple just saying that a given day is 0 (the data the service was put online) and all the next days are 1, 2, 3, and so forth. So with SETBIT it is possible to set the bit corresponding to the current day every time the user visits the site. It is possible to take the count of the bit sets on the run, this is extremely easy using a Lua script. However a fast bit count native operation can be useful, especially if it can operate on ranges, or when the string is small like in the case of days (even if you consider many years it is still extremely little data). For this reason BITOP was introduced. The command counts the number of bits set to 1 in a string, with optional range: BITCOUNT key [start end] The start/end parameters are similar to GETRANGE. If omitted the whole string is tested. Population counting is more useful when bit-level operations like AND, OR and XOR are avaialble. For instance I can test multiple users to see the number of days three users visited the site at the same time. To do this we can take the AND of all the bitmaps, and then count the set bits. For this reason the BITOP command was introduced: BITOP [AND|OR|XOR|NOT] dest_key src_key1 src_key2 src_key3 ... src_keyN In the special case of NOT (that inverts the bits) only one source key can be passed. The judicious use of BITCOUNT and BITOP combined can lead to interesting use cases with very space efficient representation of data. The implementation provided is still not tested and optimized for speed, next commits will introduce unit tests. Later the implementation will be profiled to see if it is possible to gain an important amount of speed without making the code much more complex.
-
antirez authored
The INFO output, persistence section, already contained the field describing the size of the current AOF buffer to flush on disk. However the other AOF buffer, used to accumulate changes during an AOF rewrite, was not mentioned in the INFO output. This commit introduces a new field called aof_rewrite_buffer_length with the length of the rewrite buffer.
-
antirez authored
During the AOF rewrite process, the parent process needs to accumulate the new writes in an in-memory buffer: when the child will terminate the AOF rewriting process this buffer (that ist the difference between the dataset when the rewrite was started, and the current dataset) is flushed to the new AOF file. We used to implement this buffer using an sds.c string, but sds.c has a 2GB limit. Sometimes the dataset can be big enough, the amount of writes so high, and the rewrite process slow enough that we overflow the 2GB limit, causing a crash, documented on github by issue #504. In order to prevent this from happening, this commit introduces a new system to accumulate writes, implemented by a linked list of blocks of 10 MB each, so that we also avoid paying the reallocation cost. Note that theoretically modern operating systems may implement realloc() simply as a remaping of the old pages, thus with very good performances, see for instance the mremap() syscall on Linux. However this is not always true, and jemalloc by default avoids doing this because there are issues with the current implementation of mremap(). For this reason we are using a linked list of blocks instead of a single block that gets reallocated again and again. The changes in this commit lacks testing, that will be performed before merging into the unstable branch. This fix will not enter 2.4 because it is too invasive. However 2.4 will log a warning when the AOF rewrite buffer is near to the 2GB limit.
-
antirez authored
The user @jokea noticed that the following line of code into replication.c made little sense: addReplySds(slave,sdsempty()); Investigating a bit I found that this was introduced by commit 6208b3a7 three years ago in the early stages of Redis. The code apparently is not useful at all, so I'm removing it. This change will not be backported into 2.4 so that in the rare case this should introduce a bug, we'll have a chance to detect it into the development branch. However following the code path it seems like the code is not useful at all, so the risk is truly small.
-
- 23 May, 2012 5 commits
-
-
antirez authored
The list of things to do is since long time in two places: 1) Github issues. 2) I've a private TOOD list of random ideas, what makes sense is later moved to github issues. So github is anyway the true source of things to do.
-
antirez authored
This makes the code more readable, it is still not the case to split the file itself into three different files, but the logical separation improves the readability especially since new commits are going to introduce an additional section.
-
antirez authored
Due to a change in the format of the bug report in case of crash of failed assertion the test suite was no longer able to properly log it. Instead just a protocol error was logged by the Redis TCL client that provided no clue about the actual problem. This commit resolves the issue by logging everything from the first line of the log including the string REDIS BUG REPORT, till the end of the file.
-
jokea authored
-
antirez authored
Weeks ago trying to fix an harmless GCC warning I introduced a bug in the ziplist-encoded implementations of sorted sets. The bug completely broke zuiNext() iterator, that is used in the ZINTERSTORE and ZUNIONSTORE implementation, so those two commands are no longer reliable starting from Redis version 2.4.12 and latest 2.6.0-RC releases. This commit fixes the problem and adds a regression test.
-
- 16 May, 2012 2 commits
-
-
antirez authored
In the commit upgrading jemalloc to version 3.0.0 I added the old version of Jemalloc in the 'jemalloc.orig' directory for an error. This commit removes the not useful version of jemalloc.
-
antirez authored
Full changelog here: http://www.canonware.com/cgi-bin/gitweb.cgi?p=jemalloc.git;a=blob_plain;f=ChangeLog;hb=master Notable improvements from the point of view of Redis: 1) Bugfixing. 2) Support for Valgrind. 3) Support for OSX Lion, FreeBSD.
-
- 15 May, 2012 2 commits
-
-
Salvatore Sanfilippo authored
Fix `install` target on OSX (see #495)
-
Salvatore Sanfilippo authored
Support for Illumos event ports
-
- 14 May, 2012 7 commits
-
-
Pieter Noordhuis authored
-
Dave Pacheco authored
-
Dave Pacheco authored
-
antirez authored
redis-cli.c uses the time() function to seed the PRNG, but time.h was not included. This was not noticed since sys/time.h is included and was enough in most systems (but not correct). With Ubuntu 12.04 GCC generates a warning that made us aware of the issue.
-
antirez authored
activeExpireCycle() can consume no more than a few milliseconds per iteration. This commit improves the precision of the check for the time elapsed in two ways: 1) We check every 16 iterations instead of the main loop instead of 256. 2) We reset iterations at the start of the function and not every time we switch to the next database, so the check is correctly performed every 16 iterations.
-
antirez authored
A previous commit introduced REDIS_HZ define that changes the frequency of calls to the serverCron() Redis function. This commit improves different related things: 1) Software watchdog: now the minimal period can be set according to REDIS_HZ. The minimal period is two times the timer period, that is: (1000/REDIS_HZ)*2 milliseconds 2) The incremental rehashing is now performed in the expires dictionary as well. 3) The activeExpireCycle() function was improved in different ways: - Now it checks if it already used too much time using microseconds instead of milliseconds for better precision. - The time limit is now calculated correctly, in the previous version the division was performed before of the multiplication resulting in a timelimit of 0 if HZ was big enough. - Databases with less than 1% of buckets fill in the hash table are skipped, because getting random keys is too expensive in this condition. 4) tryResizeHashTables() is now called at every timer call, we need to match the number of calls we do to the expired keys colleciton cycle. 5) REDIS_HZ was raised to 100.
-
antirez authored
Redis uses a function called serverCron() that is very similar to the timer interrupt of an operating system. This function is used to handle a number of asynchronous things, like active expired keys collection, clients timeouts, update of statistics, things related to the cluster and replication, triggering of BGSAVE and AOF rewrite process, and so forth. In the past the timer was called 1 time per second. At some point it was raised to 10 times per second, but it still was fixed and could not be changed even at compile time, because different functions called from serverCron() assumed a given fixed frequency. This commmit makes the frequency configurable, so that it is simpler to pick a good tradeoff between overhead of this function (that is usually very small) and the responsiveness of Redis during a few critical circumstances where a lot of work is done inside the timer. An example of such a critical condition is mass-expire of a lot of keys in the same second. Up to a given percentage of CPU time is used to perform expired keys collection per expire cylce. Now changing the REDIS_HZ macro it is possible to do less work but more times per second in order to block the server for less time. If this patch will work well in our tests it will enter Redis 2.6-final.
-
- 12 May, 2012 6 commits
-
-
antirez authored
-
antirez authored
If a large amonut of keys are all expiring about at the same time, the "active" expired keys collection cycle used to block as far as the percentage of already expired keys was >= 25% of the total population of keys with an expire set. This could block the server even for many seconds in order to reclaim memory ASAP. The new algorithm uses at max a small amount of milliseconds per cycle, even if this means reclaiming the memory less promptly it also means a more responsive server.
-
antirez authored
-
antirez authored
-
antirez authored
-
antirez authored
-
- 09 May, 2012 2 commits
- 06 May, 2012 3 commits