1 | #include <iostream> |
2 | #include <iomanip> |
3 | #include <vector> |
4 | |
5 | #include <unordered_map> |
6 | |
7 | #include <sparsehash/dense_hash_map> |
8 | #include <sparsehash/sparse_hash_map> |
9 | |
10 | //#define DBMS_HASH_MAP_DEBUG_RESIZES |
11 | |
12 | #include <Common/Stopwatch.h> |
13 | #include <AggregateFunctions/UniquesHashSet.h> |
14 | |
15 | #include <Core/Types.h> |
16 | #include <IO/ReadBufferFromFile.h> |
17 | #include <Compression/CompressedReadBuffer.h> |
18 | #include <Common/HashTable/TwoLevelHashTable.h> |
19 | #include <Common/HashTable/HashMap.h> |
20 | |
21 | |
22 | using Key = UInt64; |
23 | using Value = UInt64; |
24 | |
25 | |
26 | int main(int argc, char ** argv) |
27 | { |
28 | if (argc < 2) |
29 | { |
30 | std::cerr << "Usage: program n\n" ; |
31 | return 1; |
32 | } |
33 | |
34 | size_t n = atoi(argv[1]); |
35 | |
36 | std::vector<Key> data(n); |
37 | |
38 | std::cerr << "sizeof(Key) = " << sizeof(Key) << ", sizeof(Value) = " << sizeof(Value) << std::endl; |
39 | |
40 | { |
41 | Stopwatch watch; |
42 | DB::ReadBufferFromFileDescriptor in1(STDIN_FILENO); |
43 | DB::CompressedReadBuffer in2(in1); |
44 | |
45 | in2.readStrict(reinterpret_cast<char*>(data.data()), sizeof(data[0]) * n); |
46 | |
47 | watch.stop(); |
48 | std::cerr << std::fixed << std::setprecision(2) |
49 | << "Vector. Size: " << n |
50 | << ", elapsed: " << watch.elapsedSeconds() |
51 | << " (" << n / watch.elapsedSeconds() << " elem/sec.)" |
52 | << std::endl; |
53 | } |
54 | |
55 | { |
56 | Stopwatch watch; |
57 | |
58 | std::cerr << sizeof(HashMapCell<Key, Value, DefaultHash<Key>>) << std::endl; |
59 | |
60 | using Map = TwoLevelHashTable<Key, HashMapCell<Key, Value, DefaultHash<Key>>, DefaultHash<Key>, HashTableGrower<8>, HashTableAllocator>; |
61 | |
62 | Map map; |
63 | Map::LookupResult it; |
64 | bool inserted; |
65 | |
66 | for (size_t i = 0; i < n; ++i) |
67 | { |
68 | map.emplace(data[i], it, inserted); |
69 | if (inserted) |
70 | it->getMapped() = 0; |
71 | ++it->getMapped(); |
72 | } |
73 | |
74 | watch.stop(); |
75 | std::cerr << std::fixed << std::setprecision(2) |
76 | << "HashMap. Size: " << map.size() |
77 | << ", elapsed: " << watch.elapsedSeconds() |
78 | << " (" << n / watch.elapsedSeconds() << " elem/sec.)" |
79 | << std::endl; |
80 | |
81 | size_t sum_counts = 0; |
82 | size_t elems = 0; |
83 | for (const auto & kv : map) |
84 | { |
85 | sum_counts += kv.getMapped(); |
86 | ++elems; |
87 | } |
88 | |
89 | std::cerr << "sum_counts: " << sum_counts << ", elems: " << elems << std::endl; |
90 | } |
91 | |
92 | { |
93 | Stopwatch watch; |
94 | |
95 | using Map = TwoLevelHashTable<Key, HashMapCell<Key, Value, DefaultHash<Key>>, DefaultHash<Key>, HashTableGrower<8>, HashTableAllocator>; |
96 | //using Map = HashMap<Key, Value, UniquesHashSetDefaultHash>; |
97 | |
98 | Map map; |
99 | Map::LookupResult it; |
100 | bool inserted; |
101 | |
102 | for (size_t i = 0; i < n; ++i) |
103 | { |
104 | map.emplace(i, it, inserted); |
105 | if (inserted) |
106 | it->getMapped() = 0; |
107 | ++it->getMapped(); |
108 | } |
109 | |
110 | watch.stop(); |
111 | std::cerr << std::fixed << std::setprecision(2) |
112 | << "HashMap. Size: " << map.size() |
113 | << ", elapsed: " << watch.elapsedSeconds() |
114 | << " (" << n / watch.elapsedSeconds() << " elem/sec.)" |
115 | << std::endl; |
116 | |
117 | size_t sum_counts = 0; |
118 | size_t elems = 0; |
119 | for (const auto & kv : map) |
120 | { |
121 | sum_counts += kv.getMapped(); |
122 | ++elems; |
123 | |
124 | if (kv.getKey() > n) |
125 | std::cerr << kv.getKey() << std::endl; |
126 | } |
127 | |
128 | std::cerr << "sum_counts: " << sum_counts << ", elems: " << elems << std::endl; |
129 | |
130 | if (sum_counts != n) |
131 | std::cerr << "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" << std::endl; |
132 | } |
133 | |
134 | return 0; |
135 | } |
136 | |