Comment # 41 on bug 953130 from Qi Fan

(In reply to Stefan Br�ns from comment #39)
> (In reply to Qi Fan from comment #37)
> > 
> > Will information from "valgrind --tool=callgrind" help if I run it next time
> > I zypper dup?
> 
> It spends most of the time in rpm_iterate_filelist, as already said.
> 
> rpm_iterate_filelist itself could be speed up by a factor of ~2 if it were
> better optimized (it does e.g. multiple mallocs per entry, where one would
> suffice), but this helps only a little.
> 
> The big problem still is the O(n^2) behaviour (for each candidate, check
> each file in each package if it conflicts).

I think you are right. The comment like this:
https://github.com/openSUSE/libsolv/blob/bef46d75f6d2537060114eea0f3a892e958ad5e0/ext/pool_fileconflicts.c#L839
does seem to have assumed that n is pretty small. 

Some O(n) algorithm should be used instead.