You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@trafficserver.apache.org by "Alan M. Carroll" <am...@network-geographics.com> on 2018/08/13 18:28:12 UTC
Hash containers - some thoughts and recommendations
I've written up some of my notes and thoughts on hash containers and how to proceed here - https://solidwallofcode.github.io/notes/hash-table.en.html
Please respond to this email string if you have comments of your own.
Re: Hash containers - some thoughts and recommendations
Posted by Aaron Canary <ac...@oath.com.INVALID>.
Alan sent me an article by skarupke a while back. He has devoted a lot of
time to optimizing hashmaps.
Talk https://www.youtube.com/watch?v=M2fKMP47slQ
Code: flat_hash_map/bytell_hash_map.hpp at master · skarupke/flat_hash_map
<https://github.com/skarupke/flat_hash_map/blob/master/bytell_hash_map.hpp>
I'm interested if my DB can use this type of intrusive/flat allocation. It
requires that all elements can remain read-only after removed from tables
until refcount is zeroed. That is why I'm using shared_ptr. DBTable,
DBHost, DBAddr, DBAddrPort by a-canary · Pull Request #4110 ·
apache/trafficserver <https://github.com/apache/trafficserver/pull/4110>
On Fri, Aug 24, 2018 at 8:09 AM Alan Carroll
<so...@oath.com.invalid> wrote:
> I did some simple testing on IntrusiveHashMap vs. std::unordered_map. The
> first test was insertion and lookup, with 1009 items. The lookup loop was
> done 1000 times, each time looking up each item once, in a different order
> every loop, for roughly 1M lookups. The second case is a double indexed
> insert and lookup with the same set up, with the allocation of the objects
> not included (as would be the case for the shared session table). The
> std::unordered_maps stored raw pointers to the objects, not shared pointers
> to make a little faster. You can see IntrusiveHashMap is somewhat faster on
> inserts and single lookups, but on the double index lookup IntrusiveHashMap
> is almost 4x faster than std::unordered_map. This would tend to indicate
> that the double lookup is in fact a performance hit. These numbers do take
> advantage of the more efficient string lookup in IntrusiveHashMap, because
> it take store a std::string as a key but do the lookup on std::string_view
> so the caller doesn't have to construct a std::string. This would be the
> normal use case inside ATS.
>
> -O0:
> IHM populate 621540ns or 0ms
> IHM find 210755306ns or 210ms
> UM populate 832934ns or 0ms
> UM find 332646889ns or 332ms
> -O2:
> IHM populate 183626ns or 0ms
> IHM find 69232602ns or 69ms
> UM populate 191563ns or 0ms
> UM find 78888346ns or 78ms
> IHM2 populate 208932ns or 0ms
> IHM2 find 20127315ns or 20ms
> UM2 populate 254858ns or 0ms
> UM2 find 83589823ns or 83ms
>
> On Thu, Aug 23, 2018 at 5:49 PM Bryan Call <bc...@apache.org> wrote:
>
> > Memory allocations on inserting items is a property of the hash table,
> not
> > if it is intrusive vs non-intrusive (however, intrusive is this way by
> > default). Performance on a better designed hash table would be many
> times
> > faster on find, so even having to do a double find on delete isn’t a
> > performance hit.
> >
>
--
Aaron Canary
ATS - Senior Software Engineer
Re: Hash containers - some thoughts and recommendations
Posted by Alan Carroll <so...@oath.com.INVALID>.
Thing2:
1. struct Thing2 {
2. std::string _payload;
3. int _n{0};
4.
5. Thing2(std::string_view text) : _payload(text) {}
6. Thing2(std::string_view text, int x) : _payload(text), _n(x) {}
7.
8. Thing2 * _next_name {nullptr};
9. Thing2 * _prev_name {nullptr};
10.
11. struct LinkByName {
12. static Thing2*&
13. next_ptr(Thing2 *thing)
14. {
15. return thing->_next_name;
16. }
17. static Thing2 *&
18. prev_ptr(Thing2 *thing)
19. {
20. return thing->_prev_name;
21. }
22. static std::string_view
23. key_of(Thing2 *thing)
24. {
25. return thing->_payload;
26. }
27. static constexpr std::hash<std::string_view> hasher{};
28. static auto
29. hash_of(std::string_view s) -> decltype(hasher(s))
30. {
31. return hasher(s);
32. }
33. static bool
34. equal(std::string_view const &lhs, std::string_view const &rhs)
35. {
36. return lhs == rhs;
37. }
38. };
39.
40. Thing2 *_next_n{nullptr};
41. Thing2 *_prev_n{nullptr};
42.
43. struct LinkByN {
44. static Thing2*&
45. next_ptr(Thing2 *thing)
46. {
47. return thing->_next_n;
48. }
49. static Thing2 *&
50. prev_ptr(Thing2 *thing)
51. {
52. return thing->_prev_n;
53. }
54. static int
55. key_of(Thing2 *thing)
56. {
57. return thing->_n;
58. }
59. static int
60. hash_of(int n)
61. {
62. return n;
63. }
64. static bool
65. equal(int lhs, int rhs)
66. {
67. return lhs == rhs;
68. }
69. };
70. };
Re: Hash containers - some thoughts and recommendations
Posted by Walt Karas <wk...@oath.com.INVALID>.
Is the superiority of open addressing independent of usage patterns?
Does it have the same level of used versus allocated but unused
memory? Is it assumed the first lookup for the chain bucket
implementation is the head pointer of the chain?
On Fri, Aug 24, 2018 at 12:46 PM, Bryan Call <bc...@apache.org> wrote:
> I stated that a better designed hash table (not a chained hash table) would have much better performance and that a double find would not be a performance hit. The benchmark was done with two chained hash tables, which are known not to have great performance.
>
> Can you post the source code of the benchmark?
>
> -Bryan
>
>
>
>> On Aug 24, 2018, at 6:09 AM, Alan Carroll <so...@oath.com.INVALID> wrote:
>>
>> I did some simple testing on IntrusiveHashMap vs. std::unordered_map. The
>> first test was insertion and lookup, with 1009 items. The lookup loop was
>> done 1000 times, each time looking up each item once, in a different order
>> every loop, for roughly 1M lookups. The second case is a double indexed
>> insert and lookup with the same set up, with the allocation of the objects
>> not included (as would be the case for the shared session table). The
>> std::unordered_maps stored raw pointers to the objects, not shared pointers
>> to make a little faster. You can see IntrusiveHashMap is somewhat faster on
>> inserts and single lookups, but on the double index lookup IntrusiveHashMap
>> is almost 4x faster than std::unordered_map. This would tend to indicate
>> that the double lookup is in fact a performance hit. These numbers do take
>> advantage of the more efficient string lookup in IntrusiveHashMap, because
>> it take store a std::string as a key but do the lookup on std::string_view
>> so the caller doesn't have to construct a std::string. This would be the
>> normal use case inside ATS.
>>
>> -O0:
>> IHM populate 621540ns or 0ms
>> IHM find 210755306ns or 210ms
>> UM populate 832934ns or 0ms
>> UM find 332646889ns or 332ms
>> -O2:
>> IHM populate 183626ns or 0ms
>> IHM find 69232602ns or 69ms
>> UM populate 191563ns or 0ms
>> UM find 78888346ns or 78ms
>> IHM2 populate 208932ns or 0ms
>> IHM2 find 20127315ns or 20ms
>> UM2 populate 254858ns or 0ms
>> UM2 find 83589823ns or 83ms
>>
>> On Thu, Aug 23, 2018 at 5:49 PM Bryan Call <bc...@apache.org> wrote:
>>
>>> Memory allocations on inserting items is a property of the hash table, not
>>> if it is intrusive vs non-intrusive (however, intrusive is this way by
>>> default). Performance on a better designed hash table would be many times
>>> faster on find, so even having to do a double find on delete isn’t a
>>> performance hit.
>>>
>
Re: Hash containers - some thoughts and recommendations
Posted by Bryan Call <bc...@apache.org>.
My point is that if you don’t really care about top performance use std::unordered_map.
If you do care about performance using something that is performant like dense_hasg_map. It has been around since 2013 when Google open sourced it and there are benchmarks out there on it (https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.html <https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.html>).
After playing around with IntrusiveHashMap the interface is complicated and people will get it wrong. I know because I have a bug on a benchmark I wrote and haven’t figured it out. The performance is not much better than std::unordered_map. I modified your benchmark to do a string search first in the IntrusiveHashMap benchmark and the double find for std::unordered_map was 1.47x slower.
Benchmark with a larger set (N = 10k):
IHM populate 78333279ns or 78ms
IHM find 40471811802ns or 40471ms
UM populate 86525520ns or 86ms
UM find 54883270140ns or 54883ms
IHM2 populate 80184181ns or 80ms
IHM2 find 47762501485ns or 47762ms
UM2 populate 86949688ns or 86ms
UM2 find 70449403865ns or 70449ms
-Bryan
> On Aug 24, 2018, at 11:18 AM, Alan Carroll <so...@oath.com.INVALID> wrote:
>
> Here's the code, but I fail see to the point if the goal is compare
> IntrusiveHashMap to some theoretical hash map rather than the actual
> alternative hash maps that have been proposed. I thought your specific
> recommendation was to use std::unordered_map instead, so that's what I
> tested against. Also, wasn't your original objection to having to write and
> maintain our own hash containers? But now we're going to write our own
> "better designed" ones? I think this is the point at which I give up, where
> I have to beat unspecified alternate implementations and meet unspecified
> performance goals.
>
>
> 1. TEST_CASE("IntrusiveHashMapPerf", "[IntrusiveHashMap][performance]")
> 2. {
> 3. // Force these so I can easily change the set of tests.
> 4. auto start = std::chrono::high_resolution_clock::now();
> 5. auto delta = std::chrono::high_resolution_clock::now() - start;
> 6. constexpr int N_LOOPS = 1000;
> 7. constexpr int N = 1009; // prime > N_LOOPS
> 8.
> 9. std::vector<const char *> strings;
> 10.
> 11. std::uniform_int_distribution<short> char_gen {'a', 'z'};
> 12. std::uniform_int_distribution<short> length_gen { 20, 40 };
> 13. std::minstd_rand randu;
> 14.
> 15. Map ihm;
> 16. std::unordered_map<std::string, Thing> um;
> 17.
> 18. strings.reserve(N);
> 19. for ( int i = 0 ; i < N ; ++i ) {
> 20. auto len = length_gen(randu);
> 21. char *s = static_cast<char *>(malloc(len + 1));
> 22. for (decltype(len) j = 0; j < len; ++j) {
> 23. s[j] = char_gen(randu);
> 24. }
> 25. s[len] = 0;
> 26. strings.push_back(s);
> 27. }
> 28.
> 29. // Fill the IntrusiveHashMap
> 30. start = std::chrono::high_resolution_clock::now();
> 31. for (int i = 0; i < N ; ++i) {
> 32. auto thing = new Thing{strings[i], i};
> 33. ihm.insert(thing);
> 34. }
> 35. delta = std::chrono::high_resolution_clock::now() - start;
> 36. std::cout << "IHM populate " << delta.count() << "ns or " <<
> std::chrono::duration_cast<std::chrono::milliseconds>(delta).count()
> 37. << "ms" << std::endl;
> 38.
> 39. // Do some lookups
> 40. start = std::chrono::high_resolution_clock::now();
> 41. for ( int i = 0 ; i < N_LOOPS ; ++i ) {
> 42. for (int j = 0, idx = i; j < N; ++j, idx = (idx + i) % N) {
> 43. ihm.find(strings[idx]);
> 44. }
> 45. }
> 46. delta = std::chrono::high_resolution_clock::now() - start;
> 47. std::cout << "IHM find " << delta.count() << "ns or " <<
> std::chrono::duration_cast<std::chrono::milliseconds>(delta).count()
> 48. << "ms" << std::endl;
> 49.
> 50. // Fill the std::unordered_map
> 51. start = std::chrono::high_resolution_clock::now();
> 52. for (int i = 0; i < N ; ++i) {
> 53. um.emplace(strings[i], Thing{strings[i], i});
> 54. }
> 55. delta = std::chrono::high_resolution_clock::now() - start;
> 56. std::cout << "UM populate " << delta.count() << "ns or " <<
> std::chrono::duration_cast<std::chrono::milliseconds>(delta).count()
> 57. << "ms" << std::endl;
> 58.
> 59. // Do some lookups
> 60. start = std::chrono::high_resolution_clock::now();
> 61. for ( int i = 0 ; i < N_LOOPS ; ++i ) {
> 62. for (int j = 0, idx = i; j < N; ++j, idx = (idx + i) % N) {
> 63. um.find(strings[idx]);
> 64. }
> 65. }
> 66. delta = std::chrono::high_resolution_clock::now() - start;
> 67. std::cout << "UM find " << delta.count() << "ns or " <<
> std::chrono::duration_cast<std::chrono::milliseconds>(delta).count()
> 68. << "ms" << std::endl;
> 69.
> 70. // Test double indexing
> 71.
> 72. std::vector<Thing2> things;
> 73. things.reserve(N);
> 74. for ( int i = 0 ; i < N ; ++i ) {
> 75. things.emplace_back(strings[i], i);
> 76. }
> 77.
> 78. std::unordered_map<std::string, Thing2*> um_by_name;
> 79. std::unordered_map<int, Thing2*> um_by_n;
> 80.
> 81. IntrusiveHashMap<Thing2::LinkByName> ihm_by_name;
> 82. IntrusiveHashMap<Thing2::LinkByN> ihm_by_n;
> 83.
> 84. // Fill the IntrusiveHashMap
> 85. start = std::chrono::high_resolution_clock::now();
> 86. for (int i = 0; i < N ; ++i) {
> 87. ihm_by_name.insert(&things[i]);
> 88. ihm_by_n.insert(&things[i]);
> 89. }
> 90. delta = std::chrono::high_resolution_clock::now() - start;
> 91. std::cout << "IHM2 populate " << delta.count() << "ns or " <<
> std::chrono::duration_cast<std::chrono::milliseconds>(delta).count()
> 92. << "ms" << std::endl;
> 93.
> 94. // Do some lookups
> 95. start = std::chrono::high_resolution_clock::now();
> 96. for ( int i = 0 ; i < N_LOOPS ; ++i ) {
> 97. for (int j = 0, idx = i; j < N; ++j, idx = (idx + i) % N) {
> 98. Thing2 * thing = ihm_by_n.find(idx);
> 99. ihm_by_name.iterator_for(thing);
> 100. }
> 101. }
> 102. delta = std::chrono::high_resolution_clock::now() - start;
> 103. std::cout << "IHM2 find " << delta.count() << "ns or " <<
> std::chrono::duration_cast<std::chrono::milliseconds>(delta).count()
> 104. << "ms" << std::endl;
> 105.
> 106. // Fill the std::unordered_map
> 107. start = std::chrono::high_resolution_clock::now();
> 108. for (int i = 0; i < N ; ++i) {
> 109. um_by_n.emplace(things[i]._n, &things[i]);
> 110. um_by_name.emplace(things[i]._payload, &things[i]);
> 111. }
> 112. delta = std::chrono::high_resolution_clock::now() - start;
> 113. std::cout << "UM2 populate " << delta.count() << "ns or " <<
> std::chrono::duration_cast<std::chrono::milliseconds>(delta).count()
> 114. << "ms" << std::endl;
> 115.
> 116. // Do some lookups
> 117. start = std::chrono::high_resolution_clock::now();
> 118. for ( int i = 0 ; i < N_LOOPS ; ++i ) {
> 119. for (int j = 0, idx = i; j < N; ++j, idx = (idx + i) % N) {
> 120. um_by_name.find(strings[idx]);
> 121. um_by_n.find(idx);
> 122. }
> 123. }
> 124. delta = std::chrono::high_resolution_clock::now() - start;
> 125. std::cout << "UM2 find " << delta.count() << "ns or " <<
> std::chrono::duration_cast<std::chrono::milliseconds>(delta).count()
> 126. << "ms" << std::endl;
> 127.
> 128. };
>
>
> <https://apaste.info/>
>
> I think you'll find, though, that even the best designed hash map must
> still compute a hash to do a lookup and that is going to take more
> computation than IntrusiveHashMap::iterator_for. If you mean it would
> slower than that but still fast enough to not be a performance issue,
> perhaps you could elucidate what your threshold for "not a performance hit"
> is.
>
> On Fri, Aug 24, 2018 at 12:46 PM Bryan Call <bc...@apache.org> wrote:
>
>> I stated that a better designed hash table (not a chained hash table)
>> would have much better performance and that a double find would not be a
>> performance hit. The benchmark was done with two chained hash tables,
>> which are known not to have great performance.
>>
>> Can you post the source code of the benchmark?
>>
>>
Re: Hash containers - some thoughts and recommendations
Posted by Alan Carroll <so...@oath.com.INVALID>.
Here's the code, but I fail see to the point if the goal is compare
IntrusiveHashMap to some theoretical hash map rather than the actual
alternative hash maps that have been proposed. I thought your specific
recommendation was to use std::unordered_map instead, so that's what I
tested against. Also, wasn't your original objection to having to write and
maintain our own hash containers? But now we're going to write our own
"better designed" ones? I think this is the point at which I give up, where
I have to beat unspecified alternate implementations and meet unspecified
performance goals.
1. TEST_CASE("IntrusiveHashMapPerf", "[IntrusiveHashMap][performance]")
2. {
3. // Force these so I can easily change the set of tests.
4. auto start = std::chrono::high_resolution_clock::now();
5. auto delta = std::chrono::high_resolution_clock::now() - start;
6. constexpr int N_LOOPS = 1000;
7. constexpr int N = 1009; // prime > N_LOOPS
8.
9. std::vector<const char *> strings;
10.
11. std::uniform_int_distribution<short> char_gen {'a', 'z'};
12. std::uniform_int_distribution<short> length_gen { 20, 40 };
13. std::minstd_rand randu;
14.
15. Map ihm;
16. std::unordered_map<std::string, Thing> um;
17.
18. strings.reserve(N);
19. for ( int i = 0 ; i < N ; ++i ) {
20. auto len = length_gen(randu);
21. char *s = static_cast<char *>(malloc(len + 1));
22. for (decltype(len) j = 0; j < len; ++j) {
23. s[j] = char_gen(randu);
24. }
25. s[len] = 0;
26. strings.push_back(s);
27. }
28.
29. // Fill the IntrusiveHashMap
30. start = std::chrono::high_resolution_clock::now();
31. for (int i = 0; i < N ; ++i) {
32. auto thing = new Thing{strings[i], i};
33. ihm.insert(thing);
34. }
35. delta = std::chrono::high_resolution_clock::now() - start;
36. std::cout << "IHM populate " << delta.count() << "ns or " <<
std::chrono::duration_cast<std::chrono::milliseconds>(delta).count()
37. << "ms" << std::endl;
38.
39. // Do some lookups
40. start = std::chrono::high_resolution_clock::now();
41. for ( int i = 0 ; i < N_LOOPS ; ++i ) {
42. for (int j = 0, idx = i; j < N; ++j, idx = (idx + i) % N) {
43. ihm.find(strings[idx]);
44. }
45. }
46. delta = std::chrono::high_resolution_clock::now() - start;
47. std::cout << "IHM find " << delta.count() << "ns or " <<
std::chrono::duration_cast<std::chrono::milliseconds>(delta).count()
48. << "ms" << std::endl;
49.
50. // Fill the std::unordered_map
51. start = std::chrono::high_resolution_clock::now();
52. for (int i = 0; i < N ; ++i) {
53. um.emplace(strings[i], Thing{strings[i], i});
54. }
55. delta = std::chrono::high_resolution_clock::now() - start;
56. std::cout << "UM populate " << delta.count() << "ns or " <<
std::chrono::duration_cast<std::chrono::milliseconds>(delta).count()
57. << "ms" << std::endl;
58.
59. // Do some lookups
60. start = std::chrono::high_resolution_clock::now();
61. for ( int i = 0 ; i < N_LOOPS ; ++i ) {
62. for (int j = 0, idx = i; j < N; ++j, idx = (idx + i) % N) {
63. um.find(strings[idx]);
64. }
65. }
66. delta = std::chrono::high_resolution_clock::now() - start;
67. std::cout << "UM find " << delta.count() << "ns or " <<
std::chrono::duration_cast<std::chrono::milliseconds>(delta).count()
68. << "ms" << std::endl;
69.
70. // Test double indexing
71.
72. std::vector<Thing2> things;
73. things.reserve(N);
74. for ( int i = 0 ; i < N ; ++i ) {
75. things.emplace_back(strings[i], i);
76. }
77.
78. std::unordered_map<std::string, Thing2*> um_by_name;
79. std::unordered_map<int, Thing2*> um_by_n;
80.
81. IntrusiveHashMap<Thing2::LinkByName> ihm_by_name;
82. IntrusiveHashMap<Thing2::LinkByN> ihm_by_n;
83.
84. // Fill the IntrusiveHashMap
85. start = std::chrono::high_resolution_clock::now();
86. for (int i = 0; i < N ; ++i) {
87. ihm_by_name.insert(&things[i]);
88. ihm_by_n.insert(&things[i]);
89. }
90. delta = std::chrono::high_resolution_clock::now() - start;
91. std::cout << "IHM2 populate " << delta.count() << "ns or " <<
std::chrono::duration_cast<std::chrono::milliseconds>(delta).count()
92. << "ms" << std::endl;
93.
94. // Do some lookups
95. start = std::chrono::high_resolution_clock::now();
96. for ( int i = 0 ; i < N_LOOPS ; ++i ) {
97. for (int j = 0, idx = i; j < N; ++j, idx = (idx + i) % N) {
98. Thing2 * thing = ihm_by_n.find(idx);
99. ihm_by_name.iterator_for(thing);
100. }
101. }
102. delta = std::chrono::high_resolution_clock::now() - start;
103. std::cout << "IHM2 find " << delta.count() << "ns or " <<
std::chrono::duration_cast<std::chrono::milliseconds>(delta).count()
104. << "ms" << std::endl;
105.
106. // Fill the std::unordered_map
107. start = std::chrono::high_resolution_clock::now();
108. for (int i = 0; i < N ; ++i) {
109. um_by_n.emplace(things[i]._n, &things[i]);
110. um_by_name.emplace(things[i]._payload, &things[i]);
111. }
112. delta = std::chrono::high_resolution_clock::now() - start;
113. std::cout << "UM2 populate " << delta.count() << "ns or " <<
std::chrono::duration_cast<std::chrono::milliseconds>(delta).count()
114. << "ms" << std::endl;
115.
116. // Do some lookups
117. start = std::chrono::high_resolution_clock::now();
118. for ( int i = 0 ; i < N_LOOPS ; ++i ) {
119. for (int j = 0, idx = i; j < N; ++j, idx = (idx + i) % N) {
120. um_by_name.find(strings[idx]);
121. um_by_n.find(idx);
122. }
123. }
124. delta = std::chrono::high_resolution_clock::now() - start;
125. std::cout << "UM2 find " << delta.count() << "ns or " <<
std::chrono::duration_cast<std::chrono::milliseconds>(delta).count()
126. << "ms" << std::endl;
127.
128. };
<https://apaste.info/>
I think you'll find, though, that even the best designed hash map must
still compute a hash to do a lookup and that is going to take more
computation than IntrusiveHashMap::iterator_for. If you mean it would
slower than that but still fast enough to not be a performance issue,
perhaps you could elucidate what your threshold for "not a performance hit"
is.
On Fri, Aug 24, 2018 at 12:46 PM Bryan Call <bc...@apache.org> wrote:
> I stated that a better designed hash table (not a chained hash table)
> would have much better performance and that a double find would not be a
> performance hit. The benchmark was done with two chained hash tables,
> which are known not to have great performance.
>
> Can you post the source code of the benchmark?
>
>
Re: Hash containers - some thoughts and recommendations
Posted by Bryan Call <bc...@apache.org>.
I stated that a better designed hash table (not a chained hash table) would have much better performance and that a double find would not be a performance hit. The benchmark was done with two chained hash tables, which are known not to have great performance.
Can you post the source code of the benchmark?
-Bryan
> On Aug 24, 2018, at 6:09 AM, Alan Carroll <so...@oath.com.INVALID> wrote:
>
> I did some simple testing on IntrusiveHashMap vs. std::unordered_map. The
> first test was insertion and lookup, with 1009 items. The lookup loop was
> done 1000 times, each time looking up each item once, in a different order
> every loop, for roughly 1M lookups. The second case is a double indexed
> insert and lookup with the same set up, with the allocation of the objects
> not included (as would be the case for the shared session table). The
> std::unordered_maps stored raw pointers to the objects, not shared pointers
> to make a little faster. You can see IntrusiveHashMap is somewhat faster on
> inserts and single lookups, but on the double index lookup IntrusiveHashMap
> is almost 4x faster than std::unordered_map. This would tend to indicate
> that the double lookup is in fact a performance hit. These numbers do take
> advantage of the more efficient string lookup in IntrusiveHashMap, because
> it take store a std::string as a key but do the lookup on std::string_view
> so the caller doesn't have to construct a std::string. This would be the
> normal use case inside ATS.
>
> -O0:
> IHM populate 621540ns or 0ms
> IHM find 210755306ns or 210ms
> UM populate 832934ns or 0ms
> UM find 332646889ns or 332ms
> -O2:
> IHM populate 183626ns or 0ms
> IHM find 69232602ns or 69ms
> UM populate 191563ns or 0ms
> UM find 78888346ns or 78ms
> IHM2 populate 208932ns or 0ms
> IHM2 find 20127315ns or 20ms
> UM2 populate 254858ns or 0ms
> UM2 find 83589823ns or 83ms
>
> On Thu, Aug 23, 2018 at 5:49 PM Bryan Call <bc...@apache.org> wrote:
>
>> Memory allocations on inserting items is a property of the hash table, not
>> if it is intrusive vs non-intrusive (however, intrusive is this way by
>> default). Performance on a better designed hash table would be many times
>> faster on find, so even having to do a double find on delete isn’t a
>> performance hit.
>>
Re: Hash containers - some thoughts and recommendations
Posted by Alan Carroll <so...@oath.com.INVALID>.
I did some simple testing on IntrusiveHashMap vs. std::unordered_map. The
first test was insertion and lookup, with 1009 items. The lookup loop was
done 1000 times, each time looking up each item once, in a different order
every loop, for roughly 1M lookups. The second case is a double indexed
insert and lookup with the same set up, with the allocation of the objects
not included (as would be the case for the shared session table). The
std::unordered_maps stored raw pointers to the objects, not shared pointers
to make a little faster. You can see IntrusiveHashMap is somewhat faster on
inserts and single lookups, but on the double index lookup IntrusiveHashMap
is almost 4x faster than std::unordered_map. This would tend to indicate
that the double lookup is in fact a performance hit. These numbers do take
advantage of the more efficient string lookup in IntrusiveHashMap, because
it take store a std::string as a key but do the lookup on std::string_view
so the caller doesn't have to construct a std::string. This would be the
normal use case inside ATS.
-O0:
IHM populate 621540ns or 0ms
IHM find 210755306ns or 210ms
UM populate 832934ns or 0ms
UM find 332646889ns or 332ms
-O2:
IHM populate 183626ns or 0ms
IHM find 69232602ns or 69ms
UM populate 191563ns or 0ms
UM find 78888346ns or 78ms
IHM2 populate 208932ns or 0ms
IHM2 find 20127315ns or 20ms
UM2 populate 254858ns or 0ms
UM2 find 83589823ns or 83ms
On Thu, Aug 23, 2018 at 5:49 PM Bryan Call <bc...@apache.org> wrote:
> Memory allocations on inserting items is a property of the hash table, not
> if it is intrusive vs non-intrusive (however, intrusive is this way by
> default). Performance on a better designed hash table would be many times
> faster on find, so even having to do a double find on delete isn’t a
> performance hit.
>
Re: Hash containers - some thoughts and recommendations
Posted by Bryan Call <bc...@apache.org>.
Memory allocations on inserting items is a property of the hash table, not if it is intrusive vs non-intrusive (however, intrusive is this way by default). Performance on a better designed hash table would be many times faster on find, so even having to do a double find on delete isn’t a performance hit.
dense_hash_map is based on SGI’s work from over 20 years ago. flat_hash_map is a update to that and has only been talked about the last couple years and was talked about being open sourced.
-Bryan
> On Aug 23, 2018, at 12:53 PM, Alan Carroll <so...@oath.com.INVALID> wrote:
>
> 1) Because you can insert the same object, rather than pointers to the same
> object. In addition to fewer memory allocations (zero vs 2), it makes
> finding the object in the second hash table very fast - no search required
> (see IntrusiveHashMap::iterator_for). It also simplifies key management,
> because it's not necessary to split out the keys or duplicate them
> (although this is a property of the particular implementation, not
> fundamental to intrusive hash tables).
>
> 2) There's lib/ts/MT_HashTable.h. Ones in lib/ts/Map.h, such as HashMap,
> HashSet, ChainHash, StringChainHash, and NBlockHash.
>
> Yes, I don't expect my work on hash containers in TS to be on the cutting
> edge of hash table implementations. But neither is the STL AFAICT (or
> people wouldn't be using substitutes). This isn't a huge, long term
> project, it's 723 lines that are mostly comments. Interestingly, though,
> proposed methods on containers for C++20 indicate a move toward intrusive
> hash table properties for STL containers, primarily the ability to move
> nodes from one container to another without allocations.
>
> I don't have any performance measurements for IntrusiveHashMap. I will see
> if I can get time to generate some.
Re: Hash containers - some thoughts and recommendations
Posted by Alan Carroll <so...@oath.com.INVALID>.
1) Because you can insert the same object, rather than pointers to the same
object. In addition to fewer memory allocations (zero vs 2), it makes
finding the object in the second hash table very fast - no search required
(see IntrusiveHashMap::iterator_for). It also simplifies key management,
because it's not necessary to split out the keys or duplicate them
(although this is a property of the particular implementation, not
fundamental to intrusive hash tables).
2) There's lib/ts/MT_HashTable.h. Ones in lib/ts/Map.h, such as HashMap,
HashSet, ChainHash, StringChainHash, and NBlockHash.
Yes, I don't expect my work on hash containers in TS to be on the cutting
edge of hash table implementations. But neither is the STL AFAICT (or
people wouldn't be using substitutes). This isn't a huge, long term
project, it's 723 lines that are mostly comments. Interestingly, though,
proposed methods on containers for C++20 indicate a move toward intrusive
hash table properties for STL containers, primarily the ability to move
nodes from one container to another without allocations.
I don't have any performance measurements for IntrusiveHashMap. I will see
if I can get time to generate some.
Re: Hash containers - some thoughts and recommendations
Posted by Bryan Call <bc...@apache.org>.
1. How does a intrusive hash table solve the problem with having multiple indexes? You still have to insert the object to both hash tables.
2. It would be good to call out all the hash containers that are used instead of saying plethora. From what I see in the code we have these.
InkHashTable (wrapper around Tcl_HashTable)
RawHashTable (C++ wrapper around InkHashTable)
TSHashTable -> IntrusiveHashMap
unordered_map/set
Intrusive hash tables and chaining hash tables are not where I see most of the latest work being done with hash tables. Google use dense_hash_map and is moving to flat_hash_map that use advanced probing techniques.
Have you done benchmarks with IntrusiveHashMap? My guess is that the performance wouldn't be good compared to modern hash tables after reading comparable benchmarks.
-Bryan
> On Aug 13, 2018, at 11:28 AM, Alan M. Carroll <am...@network-geographics.com> wrote:
>
> I've written up some of my notes and thoughts on hash containers and how to proceed here - https://solidwallofcode.github.io/notes/hash-table.en.html
>
> Please respond to this email string if you have comments of your own.
>
Re: Hash containers - some thoughts and recommendations
Posted by Alan Carroll <so...@oath.com.INVALID>.
What happens if one table is updated, but the other isn't? Is that
permitted by the API? This does remind me that one issue with intrusive
maps is that it is much harder to protect the key from changes.
On Tue, Aug 14, 2018 at 4:20 PM Aaron Canary <ac...@oath.com.invalid>
wrote:
> https://github.com/apache/trafficserver/pull/4110
> I have also written a hashtable, intended to be an atomic map and contain
> atomic elements. read/write concurrency is handled per member of elements
> with AcidPtr.
>
> In your example "if the object has an FQDN and an IP address" then both
> tables contain shared_ptr to an atomic element (aka Extendible) and both
> have access to read/write individual fields.
>
Re: Hash containers - some thoughts and recommendations
Posted by Aaron Canary <ac...@oath.com.INVALID>.
https://github.com/apache/trafficserver/pull/4110
I have also written a hashtable, intended to be an atomic map and contain
atomic elements. read/write concurrency is handled per member of elements
with AcidPtr.
In your example "if the object has an FQDN and an IP address" then both
tables contain shared_ptr to an atomic element (aka Extendible) and both
have access to read/write individual fields.
On Mon, Aug 13, 2018 at 2:55 PM Alan Carroll
<so...@oath.com.invalid> wrote:
> You can use a layered approach to multi-index, but seems more complex than
> an intrusive container. A potential issue with that is having to duplicate
> members for keys. For instance, if the object has an FQDN and an IP address
> for keys, then if the second table uses IP address, this information isn't
> available when accessing through the first container, unless it's
> duplicated. Possible, but more expensive and error prone.
>
> The external memory management is a pre-existing condition. It also
> requires all uses of the container to remember to use this specific and
> less common access pattern. I would consider that not as easy to use and
> more prone to mistakes.
>
> On Mon, Aug 13, 2018 at 2:28 PM Walt Karas <wk...@oath.com.invalid>
> wrote:
>
> > "external memory management" can't be addressed more generally with
> > move constructors of table elements and emplace rather than insert?
> >
> > On Mon, Aug 13, 2018 at 2:23 PM, Walt Karas <wk...@oath.com> wrote:
> > > A layered approach to multiple indexes is to have all or all but one
> > > table contain pointers to the contained objects.
> > >
> > > On Mon, Aug 13, 2018 at 2:19 PM, Walt Karas <wk...@oath.com> wrote:
> > >> I was fooling with one writer / multi reader some for any data
> > >> structure. Another twist to it is to have two copies of the data
> > >> structure. You have to make updates twice, the advantage being there
> > >> is always a coherent version of the data structure available for
> > >> reading.
> > >>
> > >> http://coliru.stacked-crooked.com/a/1074bd17521d6587
> > >>
> > >>
> > >> On Mon, Aug 13, 2018 at 1:28 PM, Alan M. Carroll
> > >> <am...@network-geographics.com> wrote:
> > >>> I've written up some of my notes and thoughts on hash containers and
> > how to proceed here -
> > https://solidwallofcode.github.io/notes/hash-table.en.html
> > >>>
> > >>> Please respond to this email string if you have comments of your own.
> > >>>
> >
>
>
> --
> *Beware the fisherman who's casting out his line in to a dried up
> riverbed.*
> *Oh don't try to tell him 'cause he won't believe. Throw some bread to the
> ducks instead.*
> *It's easier that way. *- Genesis : Duke : VI 25-28
>
--
Aaron Canary
ATS - Senior Software Engineer
Re: Hash containers - some thoughts and recommendations
Posted by Alan Carroll <so...@oath.com.INVALID>.
You can use a layered approach to multi-index, but seems more complex than
an intrusive container. A potential issue with that is having to duplicate
members for keys. For instance, if the object has an FQDN and an IP address
for keys, then if the second table uses IP address, this information isn't
available when accessing through the first container, unless it's
duplicated. Possible, but more expensive and error prone.
The external memory management is a pre-existing condition. It also
requires all uses of the container to remember to use this specific and
less common access pattern. I would consider that not as easy to use and
more prone to mistakes.
On Mon, Aug 13, 2018 at 2:28 PM Walt Karas <wk...@oath.com.invalid> wrote:
> "external memory management" can't be addressed more generally with
> move constructors of table elements and emplace rather than insert?
>
> On Mon, Aug 13, 2018 at 2:23 PM, Walt Karas <wk...@oath.com> wrote:
> > A layered approach to multiple indexes is to have all or all but one
> > table contain pointers to the contained objects.
> >
> > On Mon, Aug 13, 2018 at 2:19 PM, Walt Karas <wk...@oath.com> wrote:
> >> I was fooling with one writer / multi reader some for any data
> >> structure. Another twist to it is to have two copies of the data
> >> structure. You have to make updates twice, the advantage being there
> >> is always a coherent version of the data structure available for
> >> reading.
> >>
> >> http://coliru.stacked-crooked.com/a/1074bd17521d6587
> >>
> >>
> >> On Mon, Aug 13, 2018 at 1:28 PM, Alan M. Carroll
> >> <am...@network-geographics.com> wrote:
> >>> I've written up some of my notes and thoughts on hash containers and
> how to proceed here -
> https://solidwallofcode.github.io/notes/hash-table.en.html
> >>>
> >>> Please respond to this email string if you have comments of your own.
> >>>
>
--
*Beware the fisherman who's casting out his line in to a dried up riverbed.*
*Oh don't try to tell him 'cause he won't believe. Throw some bread to the
ducks instead.*
*It's easier that way. *- Genesis : Duke : VI 25-28
Re: Hash containers - some thoughts and recommendations
Posted by Walt Karas <wk...@oath.com.INVALID>.
"external memory management" can't be addressed more generally with
move constructors of table elements and emplace rather than insert?
On Mon, Aug 13, 2018 at 2:23 PM, Walt Karas <wk...@oath.com> wrote:
> A layered approach to multiple indexes is to have all or all but one
> table contain pointers to the contained objects.
>
> On Mon, Aug 13, 2018 at 2:19 PM, Walt Karas <wk...@oath.com> wrote:
>> I was fooling with one writer / multi reader some for any data
>> structure. Another twist to it is to have two copies of the data
>> structure. You have to make updates twice, the advantage being there
>> is always a coherent version of the data structure available for
>> reading.
>>
>> http://coliru.stacked-crooked.com/a/1074bd17521d6587
>>
>>
>> On Mon, Aug 13, 2018 at 1:28 PM, Alan M. Carroll
>> <am...@network-geographics.com> wrote:
>>> I've written up some of my notes and thoughts on hash containers and how to proceed here - https://solidwallofcode.github.io/notes/hash-table.en.html
>>>
>>> Please respond to this email string if you have comments of your own.
>>>
Re: Hash containers - some thoughts and recommendations
Posted by Walt Karas <wk...@oath.com.INVALID>.
A layered approach to multiple indexes is to have all or all but one
table contain pointers to the contained objects.
On Mon, Aug 13, 2018 at 2:19 PM, Walt Karas <wk...@oath.com> wrote:
> I was fooling with one writer / multi reader some for any data
> structure. Another twist to it is to have two copies of the data
> structure. You have to make updates twice, the advantage being there
> is always a coherent version of the data structure available for
> reading.
>
> http://coliru.stacked-crooked.com/a/1074bd17521d6587
>
>
> On Mon, Aug 13, 2018 at 1:28 PM, Alan M. Carroll
> <am...@network-geographics.com> wrote:
>> I've written up some of my notes and thoughts on hash containers and how to proceed here - https://solidwallofcode.github.io/notes/hash-table.en.html
>>
>> Please respond to this email string if you have comments of your own.
>>
Re: Hash containers - some thoughts and recommendations
Posted by Walt Karas <wk...@oath.com.INVALID>.
I was fooling with one writer / multi reader some for any data
structure. Another twist to it is to have two copies of the data
structure. You have to make updates twice, the advantage being there
is always a coherent version of the data structure available for
reading.
http://coliru.stacked-crooked.com/a/1074bd17521d6587
On Mon, Aug 13, 2018 at 1:28 PM, Alan M. Carroll
<am...@network-geographics.com> wrote:
> I've written up some of my notes and thoughts on hash containers and how to proceed here - https://solidwallofcode.github.io/notes/hash-table.en.html
>
> Please respond to this email string if you have comments of your own.
>