fastest algorithm for arbitrarily irregular concave objects

[bootstrap]

I'm trying to determine what narrow-phase collision detection techniques are fastest to execute for arbitrarily irregular "concave" objects. Most importantly, I'd like to know approximately how much slower they are than convex hull techniques like GJK (executed on the convex hull of the same irregular concave objects). The emphasis I see on convex hull techniques implies that every technique that works reliably on arbitrarily irregular "concave" objects is slower than GJK. The question is, how much slower?

My "aribtrarily irregular concave" implementation is 2x to 20x slower than my GJK implementation. While the 2x~3x slower cases are not a major problem, the 20x slower cases are painful. I'm pretty sure I see a way to reduce the upper end to 10x ~ 15x slower, but not further. Hence my desire to learn whether faster approaches exist.

Thanks in advance for any ideas or tips.

PS: None of the above includes any overhead for finding first-contact time or features. With the relative performance tradeoffs I suffer now, my current approach is to perform GJK on the convex hull of objects first, then only execute my "concave" routine when a collision is found (and only when the object is not known to be convex).