{"action":"created","issue":{"url":"https://api.github.com/repos/Cyan4973/lz4/issues/126","labels_url":"https://api.github.com/repos/Cyan4973/lz4/issues/126/labels{/name}","comments_url":"https://api.github.com/repos/Cyan4973/lz4/issues/126/comments","events_url":"https://api.github.com/repos/Cyan4973/lz4/issues/126/events","html_url":"https://github.com/Cyan4973/lz4/issues/126","id":91209426,"number":126,"title":"Idea to improve decompression performance for repeated sequences with short period","user":{"login":"mtopolnik","id":490953,"avatar_url":"https://avatars.githubusercontent.com/u/490953?v=3","gravatar_id":"","url":"https://api.github.com/users/mtopolnik","html_url":"https://github.com/mtopolnik","followers_url":"https://api.github.com/users/mtopolnik/followers","following_url":"https://api.github.com/users/mtopolnik/following{/other_user}","gists_url":"https://api.github.com/users/mtopolnik/gists{/gist_id}","starred_url":"https://api.github.com/users/mtopolnik/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mtopolnik/subscriptions","organizations_url":"https://api.github.com/users/mtopolnik/orgs","repos_url":"https://api.github.com/users/mtopolnik/repos","events_url":"https://api.github.com/users/mtopolnik/events{/privacy}","received_events_url":"https://api.github.com/users/mtopolnik/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":2,"created_at":"2015-06-26T09:54:55Z","updated_at":"2015-06-26T20:58:45Z","closed_at":null,"body":"I am testing the performance of the LZ4 library through the JNI binding provided by jpountz. Currently the Java binding uses r123. I have determined a quite bad degradation of performance when the decompressed data consists of a short byte sequence repeated many times (with a period of 1-32 bytes). In reviewing the memory operations used for decompression I noticed that unaligned memory access is applied, which at least my Intel Core i7 does quite slowly when source and target are close together. As a specific example, for a period length 101 decompression reaches 16 GB/s, but for periods of 3, 5, or 7 the speed drops to 1.8 GB/s. A simple stretch of the same byte value works with 5 GB/s.\r\n\r\nTo alleviate this issue I have written a wild copying routine which does no reading at all in the copy loop for periods up to 8 and for wider periods uses word-aligned writing. For periods of 3, 5, and 7 I get at least 6 GB/s; for periods of 1, 2, 4, 8 I get ~30 GB/s (vs. 5 for the JNI version). For wider periods, say 13, I get 3.6 GB/s vs. 1.8 GB/s native.\r\n\r\nI have opened this issue in case there might be some interest in involving this kind of approach on the native LZ4 project, My code was presented at https://github.com/jpountz/lz4-java/issues/72. It is specific to a little-endian architecture, but is trivial to adapt to big-endian (swapping all `>>>` and `<<` ops)."},"comment":{"url":"https://api.github.com/repos/Cyan4973/lz4/issues/comments/115879462","html_url":"https://github.com/Cyan4973/lz4/issues/126#issuecomment-115879462","issue_url":"https://api.github.com/repos/Cyan4973/lz4/issues/126","id":115879462,"user":{"login":"Cyan4973","id":750081,"avatar_url":"https://avatars.githubusercontent.com/u/750081?v=3","gravatar_id":"","url":"https://api.github.com/users/Cyan4973","html_url":"https://github.com/Cyan4973","followers_url":"https://api.github.com/users/Cyan4973/followers","following_url":"https://api.github.com/users/Cyan4973/following{/other_user}","gists_url":"https://api.github.com/users/Cyan4973/gists{/gist_id}","starred_url":"https://api.github.com/users/Cyan4973/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Cyan4973/subscriptions","organizations_url":"https://api.github.com/users/Cyan4973/orgs","repos_url":"https://api.github.com/users/Cyan4973/repos","events_url":"https://api.github.com/users/Cyan4973/events{/privacy}","received_events_url":"https://api.github.com/users/Cyan4973/received_events","type":"User","site_admin":false},"created_at":"2015-06-26T20:58:45Z","updated_at":"2015-06-26T20:58:45Z","body":"I've been looking at your suggested improvement at https://github.com/jpountz/lz4-java/issues/72.\r\nThey look promising. But it's not trivial to grasp the entire mechanism in a single read.\r\nConsequently, I've got a few questions.\r\n\r\nThe first is about measurements. I can't guarantee that Adrien's Java version uses the same tricks as the \"C\" (native) version, nor that they are translated into the same assembler code by the jvm. Nonetheless, it's the version you compare to. So it becomes a bit more difficult to evaluate the potential improvements from your method.\r\nI see that you have also compared to the \"JNI\" version, which binds the C code. As you know, there is an additional penalty associated with JNI which becomes more and more prevalent as the sample size of data to compress becomes smaller.\r\n\r\nSo I would suggest to have some measurement on the \"C\" native version, if possible, to establish a baseline for future improvements comparisons.\r\n\r\nIf writing \"C\" code is not to your taste, you may be interested in trying the integrated benchmark utility. It's accessible using `lz4 -b filename` (presuming you have lz4 command line utility available or compiled). Filename can then be any content, including periods as you propose.\r\n\r\nI might as well have a look at it, but I don't know when, due to an already dangerously overcrowded planning.\r\n\r\nNote also that latest lz4 version, r130, is supposed to be quite a bit faster than r123. On normal data, expect some gains in the +20% range. Not sure if it's applicable to periodic data though.\r\n\r\nThe second point is a potential risk : your improvements may very well dramatically improve decoding speed for cyclic data, however, in normal circumstances, cyclic data are just a fraction (and a relatively small one) of matches. The risk is that additional logic creates more complex paths. In the end, branches and CPU mispredictions may cost more than any potential gain from the specialized branch. \r\n\r\nThis likely does not show up in specialized tests, since only one path is selected.\r\nAs a consequence, once you have validated improved results on a specific scenario, it's also important to test them within a \"more generic\" context. I recommend the _silesia corpus_ or the _calgary_ corpus for such an exercise, mainly to ensure test reproducibility.\r\n\r\nThe other questions are more technical and patchy, so let's keep them for a follow up.\r\n\r\nRegards"}}