> In a general purpose allocator, you can just store allocation metadata next to a payload so the lookup from a pointer address becomes O(1).

Yes, but the downside is that now allocator metadata pollutes the cache. It's super efficient for the allocator, but it may harm efficiency of the actual use of that memory. I believe most production allocators don't use object headers for this reason.