Java's memory management doesn't work like malloc/free at all, and that's why it's fast [1]. Even disregarding scalar replacement that means many `new` don't allocate anything on the heap, nearly all allocations are a pointer bump and objects that die don't require some active deallocation. With tracing collectors it's keeping objects
alive for a long time that requires some computational work, not deallocating them (as is the case with refcounting collectors).
An extremely simplified description of how OpenJDK's GCs work is like this: every allocation bumps the "heap end" pointer, and when memory runs out, the GC scans the objects reachable from some set of "roots", resets the allocation pointer to the start of the heap, and copies the live objects to the allocation pointer, bumping it along the way (and in the process, overwriting the dead objects). In practice, the scanning and the compaction may be done concurrently with the application, there is not just one allocation pointer (to avoid contention), and not the entire object graph needs to be scanned to free memory.
The cost of Java's good GC is virtually entirely in memory footprint (there may be some speed costs to GC in some cases, but they're offset by GC's speed benefits).
[1]: Java may indeed be slower than C on some workloads due to memory layout, but that's because of data locality, not GC. The upcoming inlined value objects will take care of that.