A number of performance problems have now been fixed and are available in Interpolations 0.12.
Just as Interpolations was “cheating” on your first example, Dierckx is “cheating” on your second. You can see this if you try
p = randperm(length(xs))
xsr = xs[p]
@btime $fit1($xs)
@btime $fit1($xsr)
This explains most of the remaining gap; Interpolations relies on searchsortedfirst to find the bracketing knots for the interpolation point, but if you traverse them in order you can find the next knot more efficiently. It would be good if someone implements this form of “cheating” for Interpolations, too.
For 1d gridded interpolation, almost all of the time is spent in searchsortedfirst. Someone who wants to make it this package faster in such cases might well take a careful look at this function and see if there are untapped performance opportunities. (As well as adding the “cheating” for sorted vector inputs.)