もしかしたら API でヘボいアルゴリズムが使われているのが原因で
C コードのアルゴリズムを読んで同じものをピュアジャバに移植したら
同じくらいの速度が出る可能性はある

同じアルゴリズムで比較しないと比べられないからね