My sudoku solver http://dancing-links.herokuapp.com/ in javascript takes roughly a tenth of the time to solve a particular puzzle when running in node/V8 than in Rhino.
There is a big difference between interpreted rhino vs. compile rhino. The Rhino wikipedia page claims compiling to byte code "... produced the best performance, often beating the C implementation of JavaScript run with just-in-time". However, the benchmarks I've seen put Rhino compiled to byte code at about 60% slower than comparable Java code.