"But this means overhead, because map calls now two functions in a row (the block means an anonymous function)."
Actually the block used by map and grep is not an anonymous function; it's just a block like if and while take. It does have a little overhead because it creates a lexical scope (it can have my variables defined within it); however not as much overhead as an anonymous sub would - calling it doesn't require stack fiddling, localizing @_, etc.
It's quite easy to confirm it's not an anonymous sub - check how caller and return behave inside a map or grep block, and compare them with what happens in an anonymous sub. return doesn't return from the map block; it returns from the outer sub.
With non-built-in functions that at first glance seem similar to map and grep (for example, List::Util's first), the block is an anonymous sub, so there is more overhead calling it. But not necessarily as much as you might think; List::Util takes advantage of an interface Perl exposes to XS code called "multicall" allowing it to repeatedly call the same anonymous sub without stack fiddling for each call - it does the stack fiddling just once, and then for each call sets @_ and runs the body of the sub.