{"action":"created","issue":{"url":"https://api.github.com/repos/HdrHistogram/HdrHistogram/issues/54","labels_url":"https://api.github.com/repos/HdrHistogram/HdrHistogram/issues/54/labels{/name}","comments_url":"https://api.github.com/repos/HdrHistogram/HdrHistogram/issues/54/comments","events_url":"https://api.github.com/repos/HdrHistogram/HdrHistogram/issues/54/events","html_url":"https://github.com/HdrHistogram/HdrHistogram/issues/54","id":62806326,"number":54,"title":"Improve memory efficiency","user":{"login":"oertl","id":9392465,"avatar_url":"https://avatars.githubusercontent.com/u/9392465?v=3","gravatar_id":"","url":"https://api.github.com/users/oertl","html_url":"https://github.com/oertl","followers_url":"https://api.github.com/users/oertl/followers","following_url":"https://api.github.com/users/oertl/following{/other_user}","gists_url":"https://api.github.com/users/oertl/gists{/gist_id}","starred_url":"https://api.github.com/users/oertl/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/oertl/subscriptions","organizations_url":"https://api.github.com/users/oertl/orgs","repos_url":"https://api.github.com/users/oertl/repos","events_url":"https://api.github.com/users/oertl/events{/privacy}","received_events_url":"https://api.github.com/users/oertl/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":5,"created_at":"2015-03-18T21:30:28Z","updated_at":"2015-03-27T14:03:56Z","closed_at":null,"body":"Ideally, to ensure a given maximum relative error r the bucket boundaries must not differ by more than a factor of (1+r). If we want to cover a range [a,b], we need at least (log(b)-log(a))/log(1+r) bins.\r\n\r\nThe allocated array sizes of HDR histogram are often much larger than this theoretical limit. For example, `((Histogram)(new DoubleHistogram(130, 4).integerValuesHistogram)).counts.length` gives 163840 while the theoretically needed number of buckets is log(130)/log(1.0001) or approximately 48678 which is more than a factor 3 less.\r\n\r\nOf course, using the optimal number of buckets, each with equal width on the logarithmic scale is not feasible, because the index function which maps a given value to the corresponding bucket would require costly evaluations of the logarithm. The key idea of the HDR histogram approach is to use slightly smaller buckets in such a way that the corresponding index function is less expensive. By nature, this optimization is at the expense of memory utilization. There are multiple effects which increase the memory costs of the HDR histogram approach:\r\n* As far as I understand the HDR approach is only able to limit the relative error to values that are a power of 1/2. That means if a maximum relative error of 0.01 needs to be guaranteed, the HDR approch must limit the relative error to (1/2)^7 = 0.0078, because (1/2)^6 = 0.0156 is too large.\r\n* Sequences of buckets of equal width (on the linear scale) range from some value to the double of that value. To cover the same range with buckets of equal width on the logarithmic scale approximately 30% less buckets would be required.\r\n* I did not analyze the code in detail. However, I guess there are some other issues that further increase the memory costs, e.g. memory alignment, array resizing, auto-scaling?\r\n\r\nSince I really liked the HDR key idea to use smaller bucket sizes to reduce indexing costs, I tried to find another index function that is more optimal regarding memory, but still cheap to evaluate. [Here](https://gist.github.com/oertl/60d52c9d308fecb5dc9d) is what I have got so far. The bucket sizes are only slightly reduced which means that not more than approx. 8% additional buckets (compared to the optimal number) are required to cover the given range while keeping the relative error below the specified maximum. First tests gave me an average recording time of about 6ns per value. Maybe the proposed approach can tackle both memory and CPU costs."},"comment":{"url":"https://api.github.com/repos/HdrHistogram/HdrHistogram/issues/comments/86949132","html_url":"https://github.com/HdrHistogram/HdrHistogram/issues/54#issuecomment-86949132","issue_url":"https://api.github.com/repos/HdrHistogram/HdrHistogram/issues/54","id":86949132,"user":{"login":"giltene","id":1914942,"avatar_url":"https://avatars.githubusercontent.com/u/1914942?v=3","gravatar_id":"","url":"https://api.github.com/users/giltene","html_url":"https://github.com/giltene","followers_url":"https://api.github.com/users/giltene/followers","following_url":"https://api.github.com/users/giltene/following{/other_user}","gists_url":"https://api.github.com/users/giltene/gists{/gist_id}","starred_url":"https://api.github.com/users/giltene/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/giltene/subscriptions","organizations_url":"https://api.github.com/users/giltene/orgs","repos_url":"https://api.github.com/users/giltene/repos","events_url":"https://api.github.com/users/giltene/events{/privacy}","received_events_url":"https://api.github.com/users/giltene/received_events","type":"User","site_admin":false},"created_at":"2015-03-27T14:03:56Z","updated_at":"2015-03-27T14:03:56Z","body":"You mat also want to compare the speed of recording a constant value rather than random smear. This will eliminate potential differences in memory access patterns and let you see the differences in the speed of the logic itself. In reality, cache misses will tend to dominate cold recordings, but another reality is that in many cases (e.g. latency measurement) values tend to be strongly multi-modal (bunched around certain mode values), so cache locality is very effective for hot recording paths, especially in lower precision cases (2 or 3 decimal points)."}}