In C or C++ you can even allocate objects on the stack, which has only the cost of increasing the stack pointer (meaning it is very cheap), and also you have precise control over the object's lifetime.
Note that by using a technique known as escape analysis, a virtual machine like the JVM can detect that the lifetime of an object is such that it doesn't leave the context of a particular method and then stack-allocate the object implicitly. That may seem like a limited optimization, but when you combine it with method inlining it gets a lot more useful. I believe the optimization is turned off by default in the Sun/Oracle JVM but can be enabled via the -XX:+DoEscapeAnalysis option. For programs that allocate large numbers of short-lived objects, it can make a significant performance difference.
Note: If you use scala, escape analysis can be particularly helpful. The "pimp my library" pattern for extending classes involves creating wrapper objects, and these can often be optimized away. http://www.decodified.com/scala/2010/08/27/scala-rich-wrappi... has more details
Often that allocation should be free - when you do a "proper" function call you'll be increasing that pointer already, and the total size of stack-bound objects in many functions can be determined at compile time.