CCL internal lock contention during multi-threaded computation

[fare]

We have a multithreaded computation that uses TYPEP a lot to filter results but is experiencing performance issues.

There's an internal recursive-lock in the CCL type system that causes reporting threads to block a noticeable amount of time. The lock is 'lock' in l1-typesys.lisp in the form that defines clear-type-cache values-specifier-type and is closed over those functions.

And our culprit is a simple TYPEP.

Not much happens while the lock is grabbed; for a (typep <obj> '<class-name>) call, it's basically an sxhash and an svref. But with many processes all filtering entries from their database session identity maps by type, there's a lot of contention.

We can refactor our application to have fewer calls to TYPEP.

But CCL implementers might be interested in some lock-free algorithm , for instance using persistent datastructures for the type cache, or some structure that only requires a lock when writing.

Xref: ITA bug 119154

[gb]

My first reaction is to be surprised that TYPEP is actually getting called often enough for this (contention on the type-cache lock) to matter.

TYPEP will actually get called:

1. If its second (type-specifier) argument isn't a constant. This situation is probably rare and often avoidable.
2. If optimization settings stress the importance of SAFETY and/or DEBUGgability at the expense of speed, in which case the behavior you observe is part of what those settings are asking for.
3. I can't think of a third case, but there could be one.

In a simple (but common and important) case like:

(defun foo (x) (typep x 'fixnum))

the call to TYPEP is ordinarily (under default optimization settings) inlined into something that checks that the low bits of X are zero and returns T if they are and NIL otherwise. Other cases involving predefined types similarly compile to inline instruction sequences that may do a little more tag/bounds/range checking, but when the type-specifier is a constant it can be translated into an internal representation of the type at compile-time (and there's no contention for the lock on the data structure that caches those translations.) Allowing that kind of compiler transform doesn't really involve a SAFETY issue in this case, but it does (in some sense) affect debugging (a naive expectation that the "call" to TYPEP can be TRACEd, for instance, would be violated.) If you're seeing heavy lock contention here because optimization settings aren't allowing calls to TYPEP to be simplified at compile-time, then you might want to consider whether the settings that you're using really meet your needs in practice.

The other case where TYPEP would likely be called at runtime is that where the type specifier isn't a constant. There can be cases where that's really necessary (such cases occur in the compiler, certainly) but the idiom is questionable enough that that needs to be considered carefully. (There's a rule of thumb that says that code that calls EVAL at runtime is probably doing so unnecessarily. There are certainly exceptions to that rule, but the rule is still helpful and a similar rule probably applies to the use of TYPEP with a variable type-specifier argument.)

Back in the day, calls to TYPEP were more common and the type cache helped performance significantly. If I'm correct in thinking that full calls to TYPEP are extremely rare (or should be in code compiled under reasonable optimization settings) then it's not clear that a caching mechanism is that important.

If you're doing full calls to TYPEP often enough for contention on the cache's lock to be important, it's likely that that's only part of the performance hit you're taking (and possibly not even a very large part.) I think that it's likely that you can avoid those calls (by compiling under less extreme optimization settings and/or avoiding calls with non-constant type-specifiers where possible.)