Sylvain Zimmer has found a way of speeding up the $$-selector in Prototype.
According to Sylvain his code is up to 20 times faster and he has even set up a test page.

Prototype's current code is quite elegant (as always!) but very slow, so I wrote an add-on that makes this function up to 20 times faster in most usual cases (tested on IE6, Firefox 1.5 and Opera).

So if you are using the $$-selector download his alternative code from his site.