The performance of memory allocators is a significant contributor to the overall performance of dynamic applications. A good memory allocator is fast, maximizes locality of access and minimizes fragmentation. In this paper we first introduce two novel memory allocators, TP and Medius, which can be tuned to optimize the three characteristics of memory allocation. These allocators can take locality enhancing hints provided automatically by the C++ STL containers used in our benchmark applications. Our TP allocator reduces the execution time of seven significant programs, by an average of 7% and 17% respectively, when compared to state-of-the-art allocators, Doug Lea's malloc and FreeBSD's PHKmalloc. We then compare the capability of various memory allocators to optimize allocation speed, locality and fragmentation. We experimentally show that these optimization goals are highly correlated and antagonistic. This means that the performance of allocators can only be the result of a trade-off between the optimization of these three performance goals. Thus we can improve overall performance by biasing our optimization towards the characteristic that matters the most (allocation speed, locality, fragmentation) for the application and computer system at hand. Our new allocators (TP and Medius) allow such selective optimization.