O(n^2) scaling in llvm symbol lookup

[yuyichao]

While fiddling #14846 with gdb folks I noticed that there's a O(n^2) scaling in our own JIT too.

The test is done on patched llvm 3.7.1 with this script which is basically emitting a lot of small functions with different names by,

for i in 1:n
    f = symbol("f$i")
    @eval $f() = $i
    @eval $f()
end

Ploting the time vs n on a log-log scale it's very clear that the O(n^2) scaling takes over for n > 10k.

The profile (done with perf since I was profiling gdb with the same command) with n = 50000 is,

and it seems that most of the time is spent in the symbol lookup (some of the other functions are also quite significant but the symbol lookup seems to be the worst).

@vtjnash and @carnaval suggested that llvm has a O(n) object file look up and we might need to replace it with our own hash table in jitlayer.cpp.

Also c.c. @Keno

[timholy]

Nice detective work as always, @yuyichao.

[vtjnash]

it's probably worthwhile to memoize the result of findSymbol in a StringMap<orc::JITSymbol> (at https://github.com/JuliaLang/julia/blob/master/src/jitlayers.cpp#L398), since we can end up jitting such an insane number of small object files and this call is linear in the number of object files that have been added

[vtjnash]

i've created a version of yuyichao's script that also emits a plot and shows my fix will be O(1): https://gist.github.com/vtjnash/89cff0605d29fe968e56 (with total compile time const on this benchmark roughly 2x the old jit, but at least with constant scaling now)

[yuyichao]

Reported upstream https://llvm.org/bugs/show_bug.cgi?id=27188