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
22using Key = UInt64;
23using Value = UInt64;
24
25
26int 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