{"action":"created","issue":{"url":"https://api.github.com/repos/sympy/symengine/issues/117","labels_url":"https://api.github.com/repos/sympy/symengine/issues/117/labels{/name}","comments_url":"https://api.github.com/repos/sympy/symengine/issues/117/comments","events_url":"https://api.github.com/repos/sympy/symengine/issues/117/events","html_url":"https://github.com/sympy/symengine/issues/117","id":27242496,"number":117,"title":"Use DSW algorithm for balanced search trees","user":{"login":"certik","id":20568,"avatar_url":"https://avatars.githubusercontent.com/u/20568?v=3","gravatar_id":"","url":"https://api.github.com/users/certik","html_url":"https://github.com/certik","followers_url":"https://api.github.com/users/certik/followers","following_url":"https://api.github.com/users/certik/following{/other_user}","gists_url":"https://api.github.com/users/certik/gists{/gist_id}","starred_url":"https://api.github.com/users/certik/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/certik/subscriptions","organizations_url":"https://api.github.com/users/certik/orgs","repos_url":"https://api.github.com/users/certik/repos","events_url":"https://api.github.com/users/certik/events{/privacy}","received_events_url":"https://api.github.com/users/certik/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/sympy/symengine/labels/performance","name":"performance","color":"fbca04"}],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":8,"created_at":"2014-02-10T05:24:30Z","updated_at":"2015-06-14T04:51:06Z","closed_at":null,"body":"We currently use `std::map` for `Mul`s. Since a typical `Mul` has just a few factors, it probably doesn't matter at all.\r\n\r\nHowever, for `Add`s, the standard `std::map` seems slower than `std::unordered_map`, so we use the latter. `std::map` uses red-black trees, that balance the tree with every insertion. A better way might be to use the [DSW algorithm](http://en.wikipedia.org/wiki/Day%E2%80%93Stout%E2%80%93Warren_algorithm), to only balance the tree once after it is constructed. [Here is](http://penguin.ewu.edu/~trolfe/DSWpaper/Code/index.html) some implementation + benchmarking code. [Here is](http://weimin-huang.com/blog/?p=127) another implementation. If it gets faster, maybe it can be used instead of `std::unordered_map`, because the advantage of using balanced search trees is that the items are sorted, which I think is essential for comparison and computing hashes."},"comment":{"url":"https://api.github.com/repos/sympy/symengine/issues/comments/111783456","html_url":"https://github.com/sympy/symengine/issues/117#issuecomment-111783456","issue_url":"https://api.github.com/repos/sympy/symengine/issues/117","id":111783456,"user":{"login":"certik","id":20568,"avatar_url":"https://avatars.githubusercontent.com/u/20568?v=3","gravatar_id":"","url":"https://api.github.com/users/certik","html_url":"https://github.com/certik","followers_url":"https://api.github.com/users/certik/followers","following_url":"https://api.github.com/users/certik/following{/other_user}","gists_url":"https://api.github.com/users/certik/gists{/gist_id}","starred_url":"https://api.github.com/users/certik/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/certik/subscriptions","organizations_url":"https://api.github.com/users/certik/orgs","repos_url":"https://api.github.com/users/certik/repos","events_url":"https://api.github.com/users/certik/events{/privacy}","received_events_url":"https://api.github.com/users/certik/received_events","type":"User","site_admin":false},"created_at":"2015-06-14T04:51:06Z","updated_at":"2015-06-14T04:51:06Z","body":"Here is another hash table implementation: http://www.clifford.at/blog/index.php?/archives/132-C++11-stdunordered_set-and-stdunordered_map-are-slower-than-a-naive-implementation.html\r\n\r\nhttps://github.com/cliffordwolf/yosys/blob/master/kernel/hashlib.h\r\n\r\nWhich might be faster.\r\n\r\nAnother one is `piranha::hash_set`: https://github.com/bluescarni/piranha/blob/master/src/hash_set.hpp\r\n\r\nOthers are available here: http://incise.org/hash-table-benchmarks.html, but they seem 5 years old."}}