Java hashmap avec un seul tableau byte[] pour toutes les clés

Question

Je dispose d'un ensemble de données assez volumineux, composé de 2,3 Go de données réparties sur 160 millions de tableaux byte[] d'une longueur moyenne de 15 octets. La valeur de chaque clé byte[] n'est qu'un int, de sorte que l'utilisation de la mémoire de près de la moitié du hashmap (qui est de plus de 6 Go) est constituée de l'overhead de 16 octets de chaque tableau d'octets.

frais généraux = en-tête de 8 octets + longueur de 4 octets arrondie par VM à 16 octets.

Mes frais généraux sont donc de 2,5 Go.

Quelqu'un connaît-il une implémentation de hashmap qui stocke ses clés byte[] (de longueur variable) dans un seul grand tableau d'octets, de sorte qu'il n'y ait pas de surcharge (à part le champ de longueur d'un octet) ?

Je préférerais ne pas utiliser de base de données en mémoire car elles ont généralement une surcharge de performance par rapport à un simple TObjectIntHashMap de Trove que j'utilise et j'accorde encore plus d'importance aux cycles de processeur qu'à l'utilisation de la mémoire.

Merci d'avance

Answer 1

Étant donné que la plupart des ordinateurs personnels ont aujourd'hui 16 Go et que les serveurs ont souvent 32 à 128 Go, voire plus, y a-t-il un réel problème avec un certain degré de frais généraux de comptabilité ?

Si nous considérons l'alternative : les données d'octets concaténées en un seul grand tableau -- nous devons réfléchir à ce à quoi les valeurs individuelles devraient ressembler, pour référencer une tranche d'un plus grand tableau.

Le plus souvent, vous commencerez par :

public class ByteSlice {
    protected byte[] array;
    protected int offset;
    protected int len;
}

Cependant, cela représente 8 octets + la taille d'un pointeur (peut-être seulement 4 octets ?) + l'en-tête de l'objet JVM (12 octets sur une JVM 64 bits). Donc peut-être un total de 24 octets.

Si nous essayons de rendre cette fonction unique et minimaliste, nous aurons toujours besoin de 4 octets pour l'offset.

public class DedicatedByteSlice {
    protected int offset;
    protected byte len;

    protected static byte[] getArray() {/*somebody else knows about the array*/}
}

Il s'agit toujours de 5 octets (probablement portés à 8) + l'en-tête de l'objet JVM. Le total est probablement toujours de 20 octets.

Il semble que le coût du déréférencement avec un décalage et une longueur, et le fait d'avoir un objet pour suivre cela, ne soient pas sensiblement inférieurs au coût du stockage direct du petit tableau.

Une autre possibilité théorique -- déstructurer la Map Key pour qu'elle ne soit pas un objet

Il est possible de concevoir la déstructuration des données "length & offset" de telle sorte qu'elles ne soient plus dans un objet. Elles sont alors passées comme un ensemble de paramètres scalaires, par exemple (length, offset) et -- dans une implémentation hashmap -- seraient stockées au moyen de tableaux de composants séparés (par exemple, au lieu d'un seul Object[] keyArray).

Cependant, je pense qu'il est extrêmement peu probable qu'une bibliothèque offre une implémentation de hashmap existante pour votre cas d'utilisation (très particulier).

Si vous parliez de la valeurs ce serait probablement inutile, car Java n'offre pas de retours multiples ou de paramètres OUT de méthode ; ce qui rend la communication impraticable sans "boxer" les données déstructurées en retour à un objet. Puisque votre question porte spécifiquement sur les clés de carte et que celles-ci sont transmises en tant que paramètres mais ne doivent pas être renvoyées, il est théoriquement possible d'envisager une telle approche.

[prolongé] Même en tenant compte de cela, cela devient délicat -- pour votre cas d'utilisation, l'API de la carte doit probablement devenir asymétrique pour la population par rapport à la consultation, car la population doit être par (offset, len) pour définir les clés, alors que la consultation pratique est probablement encore par des tableaux concrets d'octets[].

Par contre, même les ordinateurs portables les plus anciens ont 16 Go maintenant. Et le temps que vous avez passé à écrire cet article (multiplié par 4 à 10 pour le maintenir) devrait valoir bien plus que le faible coût de la RAM supplémentaire.