Home » Community » Coffee corner » Map implementation
Re: Map implementation [message #51553 is a reply to message #51552] |
Sun, 14 April 2019 19:52 |
|
mirek
Messages: 13975 Registered: November 2005
|
Ultimate Member |
|
|
Novo wrote on Sun, 14 April 2019 18:55mirek wrote on Sun, 14 April 2019 02:03If the performance is the issue, then the memory is the issue too. The game starts at L1 cache size, which can correspond to hunderds of records.
How to deal with the memory hierarchy is more or less clear (Cache-Conscious Data Structures, Cache-oblivious algorithms).
What I'm trying to say is that by using a little bit more memory you can significantly improve performance. For example, you can create a bitset of unoccupied slots. That would be overkill for a small hash table.
I made a simple test.
Vector<Index<int> > v;
Cout() << "sizeof(Index<int>): " << sizeof(Index<int>) << " bytes" << EOL;
Cout() << "Mem used: " << MemoryUsedKb() - curMU << " Kb" << EOL;
v.SetCount(v_num);
Cout() << "Created " << v_num << " empty Index<int>" << EOL;
Cout() << "Mem used: " << MemoryUsedKb() - curMU << " Kb" << EOL;
const int isize = 100;
for (int i = 0; i < isize; ++i) {
const int jsize = v_num;
for (int j = 0; j < jsize; ++j)
v[j].Add(i);
Cout() << "Added " << i + 1 << " elements" << EOL;
Cout() << "Mem used: " << MemoryUsedKb() - curMU << " Kb" << EOL;
}
Result:
sizeof(Index<int>): 80 bytes
Mem used: 0 Kb
Created 1000000 empty Index<int>
Mem used: 78128 Kb
Added 1 elements
Mem used: 237028 Kb
Added 2 elements
Mem used: 237028 Kb
Added 3 elements
Mem used: 237028 Kb
Added 4 elements
Mem used: 237028 Kb
Added 5 elements
Mem used: 237028 Kb
Added 6 elements
Mem used: 237028 Kb
Added 7 elements
Mem used: 237028 Kb
Added 8 elements
Mem used: 237028 Kb
Added 9 elements
Mem used: 397796 Kb
Added 10 elements
Mem used: 397796 Kb
...
Added 99 elements
Mem used: 2592740 Kb
Added 100 elements
Mem used: 2592740 Kb
IMHO, it is possible to do much better than this ...
Well, keep in mind that lower bound here is 400MB - that is what will cost to store keys itself. If these keys were String, which in reality is much more typical, it would be 1600MB just for values (if they are small).
Current Index overhead is on average ~20 bytes per element, which about matches what we see here. Hard to say you can do much better. E.g. typical 'collisions are linked list' implementation will use about the same number of bytes. Even open addressing will need at least 8 bytes per node if you want to have any meaningful 'payload'.
Anyway, thanks for test. You are right that you can reduce that for very specific scenarios. And next index version will probably do about 20% better.
BTW, test putting 100 * 1000000 elements into single Index will produce the same results.
Mirek
P.S.: Overall I am happy that you both started digging here as I am thinking about refactoring Index, deprecating and detuning some unsused features (ever used FindPrev? in favor of those used most frequently.
|
|
|
|
|
Map implementation
|
|
|
Re: Map implementation
By: mirek on Fri, 22 March 2019 07:18
|
|
|
Re: Map implementation
By: Novo on Wed, 27 March 2019 03:33
|
|
|
Re: Map implementation
|
|
|
Re: Map implementation
By: Novo on Tue, 02 April 2019 17:48
|
|
|
Re: Map implementation
By: Novo on Tue, 02 April 2019 18:39
|
|
|
Re: Map implementation
|
|
|
Re: Map implementation
By: mirek on Mon, 08 April 2019 22:37
|
|
|
Re: Map implementation
|
|
|
Re: Map implementation
By: mirek on Tue, 09 April 2019 17:16
|
|
|
Re: Map implementation
By: mirek on Wed, 10 April 2019 11:07
|
|
|
Re: Map implementation
|
|
|
Re: Map implementation
By: Novo on Wed, 10 April 2019 17:09
|
|
|
Re: Map implementation
By: mirek on Wed, 10 April 2019 17:37
|
|
|
Re: Map implementation
By: Novo on Sat, 13 April 2019 20:58
|
|
|
Re: Map implementation
By: Novo on Sat, 13 April 2019 21:07
|
|
|
Re: Map implementation
By: mirek on Sun, 14 April 2019 08:03
|
|
|
Re: Map implementation
By: Novo on Sun, 14 April 2019 18:55
|
|
|
Re: Map implementation
By: mirek on Sun, 14 April 2019 19:52
|
|
|
Re: Map implementation
By: mirek on Tue, 16 April 2019 12:38
|
|
|
Re: Map implementation
By: Novo on Tue, 16 April 2019 16:38
|
|
|
Re: Map implementation
By: mirek on Tue, 16 April 2019 19:33
|
|
|
Re: Map implementation
By: Novo on Tue, 16 April 2019 22:36
|
|
|
Re: Map implementation
By: Novo on Wed, 17 April 2019 05:40
|
|
|
Re: Map implementation
By: mirek on Wed, 17 April 2019 08:54
|
|
|
Re: Map implementation
By: Novo on Wed, 17 April 2019 16:13
|
|
|
Re: Map implementation
By: mirek on Wed, 17 April 2019 18:39
|
|
|
Re: Map implementation
By: mirek on Fri, 07 June 2019 13:58
|
|
|
Re: Map implementation
By: Novo on Tue, 25 June 2019 15:20
|
|
|
Re: Map implementation
By: mirek on Wed, 26 June 2019 12:07
|
|
|
Re: Map implementation
By: Novo on Mon, 01 July 2019 06:26
|
|
|
Re: Map implementation
By: mirek on Mon, 01 July 2019 17:53
|
|
|
Re: Map implementation
By: Novo on Sat, 13 April 2019 21:25
|
|
|
Re: Map implementation
By: Novo on Wed, 10 April 2019 16:13
|
|
|
Re: Map implementation
By: mirek on Wed, 10 April 2019 17:50
|
|
|
Re: Map implementation
By: Novo on Wed, 10 April 2019 16:48
|
Goto Forum:
Current Time: Thu Apr 18 12:08:36 CEST 2024
Total time taken to generate the page: 0.02108 seconds
|