Hi David, I saw a couple of your other posts related to this in Graphs.jl. It certainly is not supposed to be slow, so this is definitely worth exploring. For the benefit of others who haven't seen your posts, and for completeness, can you post or point to some of your timings?
When looking at the speed of the maximal_cliques algorithm it appears that > Sets are extremely slow, more than an order of magnitude slower than > Python. Some of this can be attributed to the fact that intersect copies > the first set and then removes the elements that don't belong, instead of > just adding the elements that occur in all sets. If we fix that, things > are still slow, and if I can trust the profiler it appears that an > inordinate amount of time is being spent creating the value array either in > the constructor or in empty!. > Usually the profiler is accurate, although occasionally Julia doesn't return the correct line numbers (off by one, etc.), and optimizations can introduce inaccuracies. > I'm not sure what Array(Nothing, n) does, but it seems to take 10 times as > long as Array(Int64, n). Is there a simple way to make this fast, or would > it be worth the trouble to make a special Set type by cloning Dict and > removing all the value code. > I'm pretty sure Array(Nothing, n) is supposed to be a no-op (or close to it--at least the array itself is supposed to take up no space, so one would hope that an empty array doesn't take any time to create). It's quite possible that is no longer the case (a regression), or possibly it was optimized away, and you're seeing the time spent on a nearby line. If you're good at reading assembly, sometimes `code_llvm()` or `code_native()` can give some hints. At a minimum, it would be worthwhile submitting a pull request for your changes to set intersection. Does the speedup you see there change depending on how much the sets overlap? (For future reference, julia-dev is probably more relevant for this type of post, although the main devs should see it here as well.) Cheers! Kevin
