It's more complicated than "functional is slower than imperative". Functional data structures are sometimes less immediately efficient, but add persistence (since they're immutable, they share subsections of the data structure, and/or have access to snapshots of past versions of the structure being modified). Whether this gives you needed features or just means extra work and cache misses depends on what you're doing. If you have a functional data structure and you want to add "undo" or backtracking, you're already most of the way there, while adding this to an imperative data structure means extra work to keep track of state changes.

_Purely Functional Data Structures_ by Chris Okasaki is, by far, the best collected resource, if you want to read further. (His thesis (http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf) is the kernel of the book.) Also, the fourth chapter of Developing Applications with Objective Caml (English translation: http://caml.inria.fr/pub/docs/oreilly-book/) discusses functional and imperative styles' strengths and weaknesses.

Reducing everything to runtime benchmarks obscures how, in practice, the trade-off is often more like "it was a huge pain in the ass to get working without bugs, but it's 2% faster" versus "it took twenty minutes and was correct on the first try". (Also, whether or not you use it in production, OCaml rules for prototyping complex data structures, in the same way Erlang does concurrency and C++ does linking errors.)