Re: [PATCH setup 2/2] Detect filename collisions between packages

[Christian Franke <Christian.Franke@t-online.de>]

Jon Turney wrote:
> ...
>>> Using std::set_intersection() on values from std::map() here is 
>>> probably
>>> a mistake. It's simple to write, but the performance is not good.
>>
>> A faster alternative which avoids set_intersection calls in a loop is 
>> possibly to use one large data structure which maps filenames to sets 
>> of packages. Using multimap<string, string> instead of the 
>> straightforward map<string, set<string>> needs possibly less memory 
>> (not tested). But for multimap it is required that file/package name 
>> pairs are not inserted twice.
>>
>> I attached a small standalone POC source file using multimap. It 
>> would also detect collisions in the already installed packages.
>
> Thanks for the ideas. It seems I really didn't think that carefully 
> about this...
>
> It seems like maybe building a map from filename to the set of package 
> names which contain it, and then finding all the filenames where that 
> set has more than one member would be a possible better implementation.

Of course this is the more obvious method and easier to implement. It is 
somewhat slower and needs more memory.

Meantime I did a quick artificial test with 10000 "packages" with 100 
"files" each and 2 collisions. This resulted in a (multi)map size if 
1000000(+2), total size of strings was ~80MB. Results:

Data structure: execution time, memory (working set)
multimap<string, string>: 1.8 seconds, 238MB
map<string, set<string>>: 2.0 seconds, 318MB

The execution time is needed for the map insertions. The final scan for 
collisions is very fast in both cases.