OSRM is astonishingly fast (it uses the Contraction Hierarchies routing algorithm, or alternatively Multi-Level Dijkstra). This is compelling for draggable routing UIs, and for large matrix calculations used in the Vehicle Routing Problem (Travelling Salesman). It also makes it easy to customise your routing weightings through Lua 'profile' scripts.

The principal downside is that the routing graph takes a lot of time and memory to prepare; runtime RAM usage is also high, though not so much. I think there's some potential for reducing its memory footprint.

Valhalla builds on the older A* algorithm, so it's not so fast (or memory-hungry), though it does make some use of hierarchies to shorten query time. Graphhopper is another, featureful routing engine designed for use with OSM data (written in Java).