MozillaDOMの不思議 style.display をいじるよりappendChildの方が早い

GreaseMonkeyをいじっていたんですが、２ちゃんねるのスレッド一覧をインクリメントサーチするスクリプトを書いてたんです。

// as は 検索したい文字列のリスト
// as[i].element は文字列に対応する A エレメント
// ↑はdocument.getElementsByTagName('A')で取得
// v は検索文字列
for( var i=0; i<as.length; i++ ){
  if( v=='' || as[i].indexOf( v )>-1 ){
    as[i].style.display='';
  }else{
    as[i].style.display='none';
  }
}

とまあ、こんなかんじ。で、そこそこ動いていたんで、気に入ってまちBBSでも動くようにしてみたら、やたらと時間がかかるです。まちBBSのスレッド一覧ではスレッド数が1000以上あるからなんでしょうね。
しかし重い。数十秒かかる。はじめは暴走したと思ってブラウザを強制終了してしまいました（GreaseMonkeyだと数秒たっても「重いですから中断しますか？」が出てこないんです）
文字列の判定にコストがかかっているのかと思って判定と表示を分離してはかってみたら、表示の方でした。さらに「エレメントの位置が後ろに行くほど（ i の値が多い程）重くなる」ようなんです。うーん、わからん。
そこで

var div=document.createElement('div');
for( var i=0; i<as.length; i++ ){
  if( v=='' || as[i].indexOf( v )>-1 ){
    div.appendChild( as[i].element );
  }
}
// olddiv は昔のdiv
olddiv.style.display='none';
olddiv.parentNode.insertBefore( div, olddiv );
olddiv = div;

としてみると一瞬で済んでしまう。
なぜだろう。DOMツリーの移動の方がコスト高の気がするんだが…
検索の場合はヒットする方が数が少ないから、という理由も考えたんですが、v="" の時、つまり全部がヒットする場合でも、前のものより圧倒的に早いです（1秒以下）。styleをいじるたびに全エレメントの一計算をし直してるんでしょうか…でも「エレメントの位置が後ろに行くほど重くなる」のは逆の気がするし…
というあいかわらずどこで有効なのかわからないJavaScript Tipsでした（誰の文体だ？）。