A large number of asynchronous sleep calls result in an unexplained slowdown

[amitmurthy]

  | | |_| | | | (_| |  |  Version 0.5.0-dev+699 (2015-10-10 07:52 UTC)
 _/ |\__'_|_|_|\__'_|  |  Commit ba135b2* (0 days old master)
|__/                   |  x86_64-apple-darwin14.5.0

julia> @time @sync begin
         for i in 1:10^6
           @async 1
         end
       end

  2.235673 seconds (7.05 M allocations: 752.358 MB, 12.85% gc time)

julia> @time @sync begin
         for i in 1:10^6
           @async 1
         end
       end
  2.398916 seconds (7.00 M allocations: 749.408 MB, 32.83% gc time)

julia> @time @sync begin
         for i in 1:10^6
           @async 1
         end
       end
  2.036422 seconds (7.00 M allocations: 741.408 MB, 23.95% gc time)

julia> @time @sync begin
         for i in 1:10^6
           @async sleep(0.01)
         end
       end
  8.491163 seconds (18.02 M allocations: 1.901 GB, 20.81% gc time)

julia> @time @sync begin
         for i in 1:10^6
           @async sleep(0.01)
         end
       end
 12.585165 seconds (18.00 M allocations: 1.871 GB, 13.08% gc time)

julia> gc()

julia> @time @sync begin
         for i in 1:10^6
           @async sleep(0.01)
         end
       end
 30.350741 seconds (18.00 M allocations: 1.887 GB, 4.34% gc time)

julia> @time @sync begin
         for i in 1:10^6
           @async sleep(0.01)
         end
       end
118.704723 seconds (18.00 M allocations: 1.871 GB, 1.07% gc time)

While no one may call sleep a million times, it may be the result of a deeper libuv issue.

[vtjnash]

From profiling, I think the bug here is actually a deeper issue with ObjectIdDict (not libuv): In particular, while it's typical performance seems to be roughly equivalent to Base.Dict, I think I was seeing worst case performance on this benchmark of sometimes 100x slower (mostly at src/table.c:112 in jl_table_peek_bp).

[JeffBezanson]

It looks like the problem is that ObjectIdDict does not hold up well under heavy deletion. We don't rehash it when there are many deleted items.