IntervalOptimisation.jl and threads gives lock conflicts

New to Julia
, ,
1

Hi, in a project I’m working on, I need to run many, many small optimizations. I like to do this by using Threads.@threads, which typically cuts down my runtime by a factor 2-4 for the problems I’m looking at. However, when I’m using IntervalOptimisation, I don’t see this speed-up, and instead I get many lock conflicts, see the following MWE:

using IntervalArithmetic, IntervalOptimisation

function RunTest()
    rosenbrock(x, p) = (p[1] - x[1])^2 + p[2] * (x[2] - x[1]^2)^2
    x0 = [0.5, 0.5]
    _p = [1.0, 100.0]
     
    @time for n in 1:10000
        global_min, minimisers = minimise(x -> n + rosenbrock(x, _p) - n, (0..1) × (0..1))
    end
    @time Threads.@threads for n in 1:10000
        global_min, minimisers = minimise(x -> n + rosenbrock(x, _p) - n, (0..1) × (0..1))
    end
end

RunTest()

Which gives

  6.802763 seconds (193.07 M allocations: 7.755 GiB, 4.82% gc time)
  5.990980 seconds (193.26 M allocations: 7.393 GiB, 3.02% gc time, 2602642 lock conflicts, 3.75% compilation time)

I’m not too knowledgeable on this, but I’m going to guess that the limited increase in speed is due to the lock conflicts. I couldn’t find if this is a known issue, but I was wondering if anyone knows a work-around?

2

That one is for @dpsanders.

3

Sorry I don’t know how these locks work.
What could be causing the conflicts?

4

These lock conflict reports are when a lock request on a ReentrantLock (not a SpinLock) isn’t immediately granted because it’s held by another task.
Added in Add count of lock conflicts to `@time` etc. Add `@lock_conflicts` by IanButterworth · Pull Request #52883 · JuliaLang/julia · GitHub

Also, if it’s not clear where the conflicts are coming from, this might be helpful add way to log where lock conflicts are by IanButterworth · Pull Request #55120 · JuliaLang/julia · GitHub

5

Is it any different if you use tuples instead of vectors? Also, x0 appears to be unused.

6

You’re right, x0 can just be removed; that was left over from other optimization methods that I was comparing against. Using _p = (1.0, 100.0) doesn’t fix the problem. I’m not sufficiently knowledgeable about the internals of multi-threading in Julia and the internals of IntervalOptimisation.jl to see if there is an easy fix at this point. I’m currently not using IntervalOptimisation in my project, so there is no need per se on my end to get this fixed, but I did want to rapport the issue as it surprised me that IntervalOptimisation.jl had these lock conflicts while other optimization methods (e.g. NLOpt) didn’t seem to have these lock conflicts.

7

Perhaps it’s a typo, but i was suggesting:

_p = (1.0, 100.0)

that is, a tuple.

8

Thanks, that was a typo indeed; _p = (1.0, 100.0) didn’t resolve the issue. I’ve modified my response.

9

Intuitively, the optimization algorithm wouldn’t do something with cross optimizers locking. So what’s left is the allocations which are indeed common in the internal data structures (HeapedVectors or something).
Having allocations lock across threads seems also intuitive without special allocation arenas.

10

Ah, thanks @Dan. I had forgotten about HeapedVectors.

That code is all ancient and should be ripped out and replaced with some kind of more standard data structure! Do the ones e.g. in DataStructures play well with locks?

1 Like
11

Skimmed the code of HeapedVectors and the equivalent BinaryHeap in DataStructures. The DataStructures looks more mature. Especially, it doesn’t use recursion. Recursion can be problematic as it plays with the call stack and the compiler doesn’t always know how to optimize it.

So a refactor with DataStructures sounds like a good idea.

1 Like