Speed up AutoDiffXd substantially

[sherm1]

We believe the primary performance problem with AutoDiffXd is the absurd amount of heap malloc/free it requires during computation. Why is that expensive?

• locking for thread safety
• searching for a suitably-sized block on malloc(); combining blocks on free()

Ideas:

• write a fixed-block-size memory manager (a.k.a. memory pool), with optional thread safety. Modify our version of AutoDiffScalar to use it instead of new/delete.
• add missing move semantics to AutoDiffScalar operators to avoid unnecessary reallocations.

The bespoke memory manager would work because all the derivative blocks we need are the same size during a computation. That means:

• no searching for the right size
• no block combining on free
• the first free block is always acceptable.

The latter point means good (hardware) cache behavior because the free list is essentially a stack -- the last one freed is the first one used and is likely still in the cache.

With careful implementation both allocation and freeing could be inline operations using only a few assembly instructions.

Also see discussion in issue #7039.

[jwnimmer-tri]

Alejandro asked me about this on slack earlier. I think you both underestimate how well current off-the-shelf allocators perform. How about a benchmark to show how bad the current one is? Or if glibc malloc really is bad, the first thing to do is not write your own allocator! It's to try jemalloc or tcmalloc or whatever other off-the-shelf one already exists.

[sherm1]

The underlying assumption here is that AutoDiffXd(100) is much slower than AutoDiff100d. I have not measured that myself, so it has the status of rumor at the moment! But assuming it's true, heap allocation must be a lot slower than stack memory allocation.

Replacing heap allocation for all of Drake is a much more drastic step than just making AutoDiffXd work better by using a fixed-size pool. It could be worth a try though.

In any case this is a quantitative question and what we are really lacking at the moment is a repeatable benchmark problem showing that stack-allocated AutoDiff is much faster than heap-allocated. If we had that we could play with the heap allocation to see what it takes to get it close to stack-allocated performance.

[amcastro-tri]

I will add heap/stack-allocated AutoDiff tests to the benchmark I'm writing. I think @jwnimmer-tri has a good point on that we should just measure it.

[jwnimmer-tri]

Actually the first thing I would do (in terms of fixing the code) is teach AutoDiffXd about value categories. At the moment, every operation makes a copy (sometimes more than one!) of the derivatives vector. If it were move-enabled, we would be hitting the heap much less often, no matter the allocator.

(I still agree that having a benchmark is the first step.)

[sherm1]

If it were move-enabled ...

I agree. That's actually one of my biggest complaints about Eigen. It uses horribly complicated expression templates to achieve what could mostly have been done with move semantics. I believe that is due to it predating &&. We are overdue for a modern-C++ matrix library.

[jwnimmer-tri]

It has move on the Matrix classes, just not on the ADS class.

[sherm1]

TIL with some relief that thread local storage is (allegedly) as fast as local storage. That bodes well for a possible AutoDiffScalarX implementation that maintains its own pool of temporaries.

FYI @rpoyner-tri please see the above discussion.

[EricCousineau-TRI]

From #13675:

Related issues

• MultiBody dynamics, inertia, and autodiff benchmarking #10322

Related discussions

• Benchmarking in dairlib:
  • https://gist.github.com/mposa/99e17f7b043ad737cf429c6801311da2
  • https://drakedevelopers.slack.com/archives/C3L92BM2Q/p1590255574041300

[jwnimmer-tri]

Would it be fair to say that this is not "priority: high" anymore?

[sherm1]

Sigh. It's going to be a much longer slog than we hoped. Still highly desirable and we should keep at it. Lowering to Medium.