Why the downvote?

The smaller the strings, the more strings you can allocate before triggering a garbage collection. Also, the smaller the objects, the less copying is needed when promoting survivors.

And the more you can allocate in a thread local allocation buffer before your bump allocator has to request a new TLAB.

I would imagine most of the time would likely be spent traversing the object graph (i.e. chasing references), making it O(number of references) rather than O(allocated size)

Larger allocations causes the heap to fill up faster, causing garbage collection to happen more often (more traversing the graph). Also, a generational garbage collector like you have in Java will copy survivors to a new heap. The larger the object, the more you will have to copy.