During the early years of Emacs, the main complaints from users about the simple mark&sweep algorithm were the GC pauses. These were solved very simply in Emacs 19.31 by removing the messages that indicated when GC was in progress. Since then complaints about the performance of the GC have been rare. Most of them have to do with the amount of time wasted in the GC during initialization phases, where a lot of data is allocated without generating much garbage.

At 300 baud, I bet the GC messages took longer to display than the GC itself.