JavaScript, le tri avec le second paramètre est plus rapide

Question

J'ai fait un petit test, et j'ai découvert que array.sort(function(a, b) { return a - b; }); est beaucoup plus rapide que array.sort(); en JavaScript. Les résultats ont été assez choquants, environ 1,7 fois plus rapide dans IE9, 1,6 fois dans FF7 et 6,7 fois dans Chrome.

De plus, en implémentant quicksort par moi-même dans JS, j'ai trouvé que c'était encore plus rapide que les deux méthodes mentionnées ci-dessus. (Deux implémentations différentes, l'une accepte une fonction de comparaison en tant que paramètre, l'autre non, les deux étaient plus rapides.)

Y a-t-il une explication raisonnable?

EDIT: Mes implémentations:

Non comparateur:

function quickSort(array, from, to) { 
    if(typeof from === 'undefined') { 
     from = 0; 
     to = array.length - 1; 
    } 
    else if(typeof to === 'undefined') { 
     to = array.length - 1; 
    } 

    if(to - from < 1) { 
     return; 
    } 

    var i = from, pivot = to, t; 

    while(i < pivot) { 
     if(array[i] > array[pivot]) { 
      t = array[i]; 
      array[i] = array[pivot - 1]; 
      array[pivot - 1] = array[pivot]; 
      array[pivot] = t; 
      pivot--; 
     } 
     else { 
      i++; 
     } 
    } 

    quickSort(array, from, pivot - 1); 
    quickSort(array, pivot + 1, to); 
} 

Avec comparateur:

function quickSortFunc(array, sortfunc, from, to) { 
    if(typeof from === 'undefined') { 
     from = 0; 
     to = array.length - 1; 
    } 
    else if(typeof to === 'undefined') { 
     to = array.length - 1; 
    } 

    if(to - from < 1) { 
     return; 
    } 

    var i = from, pivot = to, t; 

    while(i < pivot) { 
     if(sortfunc(array[i], array[pivot]) > 0) { 
      t = array[i]; 
      array[i] = array[pivot - 1]; 
      array[pivot - 1] = array[pivot]; 
      array[pivot] = t; 
      pivot--; 
     } 
     else { 
      i++; 
     } 
    } 

    quickSortFunc(array, sortfunc, from, pivot - 1); 
    quickSortFunc(array, sortfunc, pivot + 1, to); 
} 

Answer 1

Il y a deux facteurs qui entrent en jeu:

D'abord, comme Felix Roi mentionné dans les commentaires, la méthode de tri natif convertit chaque membre du groupe en une chaîne avant de comparer. L'utilisation de function(a, b) { return a - b; } est beaucoup plus rapide si tous les membres du groupe (ou la plupart) sont des nombres.

Deuxièmement, l'algorithme de tri est implementation dependent. Comme vous le savez peut-être, quicksort fonctionne vraiment mal si vous insérez un nouvel élément dans un tableau déjà trié. C'est peut-être pour cette raison que WebKit a décidé d'implémenter Selection Sort à la place. Mais n'ayez pas peur, l'aide est proche! Quelqu'un déjà forked WebKit to fix this

Answer 2

De nombreuses raisons entreraient en jeu. Ne pas avoir à vérifier le type de variable est l'un d'entre eux et un seul d'entre eux. Et votre implémentation rend l'optimiseur heureux. Il fonctionne avec un tableau dense, il ne fonctionne qu'avec des nombres, les variables sont bien délimitées et réutilisées. Non, non, pas d'évaluation, pas de variables magiques, de propriétés, de fonctions ou de types. Cela optimiserait bien.

Toutefois, si vous avez essayé d'implémenter des méthodes de tableau indépendantes du type et indépendantes de la commande, telles que reverse(), vous pouvez également constater que votre propre implémentation est plus rapide. Au moins le mien est.

Pourquoi?

JavaScript est fortement optimisé de nos jours, en particulier sur les boucles et les opérations répétées sur le même type de choses - nombre, chaîne, même des objets de même forme (c'est compliqué). Dans des cas extrêmes, le moteur d'exécution alignerait vos fonctions, ignorerait les vérifications de type variable et, dans le cas de Chrome, conserverait vos numéros dans les registres pour que votre boucle soit aussi rapide que C.

Wow.

Mais ces optimisations n'ont décollé que ces dernières années. À ce moment, les fonctions natives ne sont pas encore aussi optimisables que le code utilisateur. Ils ne subissent pas autant d'optimisations dynamiques que le code utilisateur.

Là, je l'ai dit.

Actuellement, le code utilisateur peut s'exécuter plus rapidement que l'implémentation native, notamment parce que le programmeur connaît les flux de données qui s'y trouvent.Mais cela peut être temporaire. Je vais m'arrêter ici et vous laisser décider si vous voulez créer votre propre bibliothèque de tableaux.

Answer 3

C'est une conjecture assez sauvage, mais le coup de performance peut-il se produire en raison du tri natif, vérifiant si les attributs passés sont vierges ou nuls ... D'où la recherche de la fonction par défaut (au lieu d'une fois) ...

Il pourrait être un problème d'optimisation erronée, qui pourrait être résolue si elle est vraie ... Espérons que quelqu'un dans Firefox dev peut répondre :)