Overview Examples Screenshots Comparisons Applications Download Documentation Tutorials Bazaar Status & Roadmap FAQ Authors & License Forums Funding Ultimate++
Search on this site
Search in forums

Home » Community » Coffee corner » Map implementation
Re: Map implementation [message #51522 is a reply to message #51521] Tue, 09 April 2019 14:57
 cbpporter Messages: 1400Registered: September 2007 Senior Contributor
I re-implemented Index (copy&paste, trancode and cleanup) and should be a good starting point since it is smaller and simpler than a lot of maps out there.

I'll test mine thoroughly and benchmark, but before I benchmarked U++ vs. set vs. multiset, just to set my expectations accordingly.

U++ is pretty fast when compared to STL, but it does have exponential growth. With many items, in some tests, when multiplying items by 10, STL will go from like 250ms to 320, while Index will go from 250ms to 2 minutes .

I used this simple test:
```	const int SEQ = 10;
const int MAX = 3000000 * SEQ;
const int JUMP = 100;

{
Index<int> ind;

StopWatch ts;

for (int j = 0; j < MAX; j += JUMP)
for (int i = j; i < j + SEQ; i++) {
//ind.Debug(Cout());
}

Cout() << "U++ add " << ts.Elapsed() << "\n";

ts.Reset();

int count = 0;
for (int i = 0; i < MAX; i++)
if (ind.Find(i) != -1)
count++;

Cout() << "U++ find " << ts.Elapsed() << "\n";
Cout() << count << "\n";
}

{
std::set<int> ind;

StopWatch ts;

for (int j = 0; j < MAX; j += JUMP)
for (int i = j; i < j + SEQ; i++) {
ind.insert(i);
//ind.Debug(Cout());
}

Cout() << "set add " << ts.Elapsed() << "\n";

ts.Reset();

int count = 0;
for (int i = 0; i < MAX; i++)
if (ind.find(i) != ind.end())
count++;

Cout() << "set find " << ts.Elapsed() << "\n";
Cout() << count << "\n";
}

{
std::multiset<int> ind;

StopWatch ts;

for (int j = 0; j < MAX; j += JUMP)
for (int i = j; i < j + SEQ; i++) {
ind.insert(i);
//ind.Debug(Cout());
}

Cout() << "multiset add " << ts.Elapsed() << "\n";

ts.Reset();

int count = 0;
for (int i = 0; i < MAX; i++)
if (ind.find(i) != ind.end())
count++;

Cout() << "multiset find " << ts.Elapsed() << "\n";
Cout() << count << "\n";
}```

Is this an OK first artificial benchmark?

For MAX as large as the example, this is the starting point where U++ begins to loose vs. STL.

Next I need to compare memory usage...

Edit: I broke the benchmark into add and find, and the exponential growth for many items is at the find phase.

[Updated on: Tue, 09 April 2019 15:03]

Report message to a moderator

 Map implementation By: cbpporter on Thu, 21 March 2019 16:32 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 By: cbpporter on Tue, 02 April 2019 14:13 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 By: cbpporter on Mon, 08 April 2019 13:57 Re: Map implementation By: mirek on Mon, 08 April 2019 22:37 Re: Map implementation By: cbpporter on Tue, 09 April 2019 14:57 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 By: cbpporter on Wed, 10 April 2019 11:39 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
 Previous Topic: [Skylark][witz] How would you do this Next Topic: Strange Architecture
Goto Forum:

Current Time: Thu Apr 02 14:57:21 CEST 2020

Total time taken to generate the page: 0.01708 seconds