J'ai écrit le code mentionné ci-dessous. Le code vérifie le premier bit de chaque octet. Si le premier bit de chaque octet est égal à 0, il concaténe cette valeur avec l'octet précédent et le stocke dans une variable variable variable variable. Ici, POS pointe des octets d'un entier. Un entier dans ma mise en œuvre est UINT64_T et peut occuper jusqu'à 8 octets.
uint64_t func(char* data)
{
uint64_t var1 = 0; int i=0;
while ((data[i] >> 7) == 0)
{
variable = (variable << 7) | (data[i]);
i++;
}
return variable;
}
6 Réponses :
Une petite optimisation serait: bitwise et est généralement plus rapide qu'un décalage. Cela dépend bien sûr de la plate-forme et il est également possible que le compilateur fera cette optimisation elle-même.
En dehors de cela ... Pouvez-vous suggérer une autre optimisation ... j'ai vraiment besoin de cela
Je serais choqué si un compilateur moderne n'a pas déjà fait cela.
@MOOINGDUCK J'ai vérifié avec ma machine avec g ++ 4.6 et il ne remplaçait pas les instructions. Peut-être qu'ils sont coûteux de manière équivalente?
C'est ce que je présume. L'optimiseur est assez intelligente pour faire ce genre de chose si il était meilleur
Sur mon G ++ 4.6.4 il remplacé cette condition tout le equalivalent de pos [i]> = 0
Votre code est problématique première chose mineure: second: vous n'affirmez pas que Vous ne lisez pas au-delà de la limite de troisième: si Le troisième point nous aide en fait de nous: en conclusion: nous avons séparé la logique et s'est débarrassé de toutes les entrées mis au rebut . L'accélération dépend des données réelles que vous avez. Si des entrées de lot sont supprimées, vous économisez beaucoup d'écritures sur Autre chose: surtout, si une fonction est appelée massivement, la meilleure optimisation que vous pouvez faire est l'appeler moins. Peut-être que vous pouvez avoir proposé une condition supplémentaire qui rend l'appel de cette fonction inutile. garder à l'esprit que si vous utilisez réellement 10 valeurs, la première valeur finit par être tronquée. 64 bits signifie qu'il y a 9 valeurs avec leurs 7 bits d'informations complètes sont représentés, laissant exactement un bit laissé ennemi le dixième. Vous voudrez peut-être passer à i doit être non signé. POS . Par exemple. Si toutes les valeurs de votre POS sont 0 , alors vous atteindrez pos posidifier [taille] où taille est le Taille de la matrice, d'où vous invoquez un comportement non défini. Vous devez transmettre la taille de votre matrice à la fonction et vérifier que i est plus petit que cette taille. pos positique [i] a Bit le plus significatif égal à zéro pour i = 0, .., k avec k> 10 , puis le travail précédent est rejeté (en appuyant sur l'ancienne valeur de var1 ). var1 avec cette approche. uint128_t .
Je viens de corriger un petit problème avec mon code: car vous ne changez que par 7 bits, pas 8 bits, 9 articles et un bit peuvent être tenus. Je suppose char_bit == 8 ici, bit c'est la chose habituelle de toute façon. Vous voudrez peut-être changer cela si vous voulez être une plate-forme vraiment indépendante.
Je ne vois pas pourquoi i devrait être non signé; Il n'y a rien de spécial à ce sujet, de sorte que la "bonne pratique" habituelle serait d'utiliser int . (Bien sûr, la pratique idiomatique habituelle en C ++ serait d'utiliser des pointeurs.)
@Jameskanze Bonne pratique serait non signée car nous ne voulons jamais augmenter i . Il n'y a aucune raison d'utiliser un signe ici. La chose idiomatique en C ++ serait d'utiliser un conteneur et d'itérer ou de commencer et de mettre fin aux itérateurs imitateurs.
La conception de la langue est que int être utilisé à moins d'une très forte raison de ne pas le faire. Ici, il n'y a aucune raison de ne pas utiliser int , la meilleure pratique consiste donc à l'utiliser. Pour le code actuel à présent, il ne fait aucune différence réelle (sauf que tout sauf int envoie le mauvais message au lecteur), mais les types non signés en C ++ ont une sémantique plutôt intuitive et sont mieux évité pour les valeurs arithmétiques.
Mais nous convenons que la solution idiomatique utiliserait des pointeurs (qui sont des itérateurs d'accès aléatoire). On peut faire valoir si c'est une bonne idiome (bien que dans ce cas, je préfère cela), mais c'est omniprésent.
@Jameskanze "La conception de la langue est que l'INT est utilisée à moins d'une raison très forte de ne pas" Avez-vous quelque chose à soutenir cette déclaration? Je suis fortement en désaccord avec cela. Pourquoi quels conteneurs standardieniraient-ils un entier non signé comme une taille alors?
Kernighan et Richie. Stroustrup. En ce qui concerne les conteneurs standard, il y a beaucoup d'histoire impliquée, mais la raison principale est sans doute le fait qu'ils ont été développés sur une machine 16 bits, où le bit supplémentaire pour la valeur a fait une différence.
@Jameskanze Pouvez-vous faire référence à une instruction (à jour), c'est-à-dire un lien vers l'interview, etc.? Je ne vois tout simplement aucune raison d'utiliser des entiers signés pour cela. Les entiers non signés sont meilleurs: pas de baisse de la performance, mais augmentez l'indépendance de la plate-forme (vous avez mentionné des machines 16 bits). Les divisions peuvent même être plus rapides pour les types non signés. int dit "Cela pourrait être négatif aussi". Les entiers non signés sont nés pour être des indices
J'ai vu la déclaration à K & R I. Je n'ai pas mes livres à portée de main ici pour citer, mais si vous regardez la programmation de STROSTRUP - Principes et pratiques utilisant C ++ , vous verrez que vous verrez que Il n'utilise aucun type non signé. À un programmeur C ++ expérimenté, non signé dit manipulation de bits ou modulo arithmétique. Unsigné est une erreur sujette, voir aristeia.com/papers/c++reportcolumns/ sep95.pdf .
@Jameskanze Bien oui, vous devez faire attention avec des types non signés, mais vous ne changez que le temps que vous devez faire attention. non signé peut être utilisé pour des manipulations de bits et des arithmétiques modulo, mais pas exclusivement. Beeing Un programmeur C ++ expérimenté moi-même, je ne les utilises que rarement à cette fin, c'est-à-dire que je n'ai qu'une telle demande. Le plus souvent, je les utilise pour exprimer l'intention d'avoir représenté un nombre naturel (E.G. Index, taille, ...). Je suppose que c'est une question de goût sur lequel nous sommes en désaccord.
Je n'ai testé que cela minimalement; Je suis heureux de résoudre des problèmes avec ça. Avec des processeurs modernes, vous souhaitez biais votre code fortement vers des branches facilement prédits. Et si vous pouvez lire en toute sécurité les 10 prochains octets d'entrée, il n'y a rien à sauver en gardant leurs lectures par des branches conditionnelles. Cela me conduit au code suivant:
// fast uleb128 decode
// assumes you can read all 10 bytes at *data safely.
// assumes standard uleb128 format, with LSB first, and
// ... bit 7 indicating "more data in next byte"
uint64_t unpack( const uint8_t *const data )
{
uint64_t value = ((data[0] & 0x7F ) << 0)
| ((data[1] & 0x7F ) << 7)
| ((data[2] & 0x7F ) << 14)
| ((data[3] & 0x7F ) << 21)
| ((data[4] & 0x7Full) << 28)
| ((data[5] & 0x7Full) << 35)
| ((data[6] & 0x7Full) << 42)
| ((data[7] & 0x7Full) << 49)
| ((data[8] & 0x7Full) << 56)
| ((data[9] & 0x7Full) << 63);
if ((data[0] & 0x80) == 0) value &= 0x000000000000007Full; else
if ((data[1] & 0x80) == 0) value &= 0x0000000000003FFFull; else
if ((data[2] & 0x80) == 0) value &= 0x00000000001FFFFFull; else
if ((data[3] & 0x80) == 0) value &= 0x000000000FFFFFFFull; else
if ((data[4] & 0x80) == 0) value &= 0x00000007FFFFFFFFull; else
if ((data[5] & 0x80) == 0) value &= 0x000003FFFFFFFFFFull; else
if ((data[6] & 0x80) == 0) value &= 0x0001FFFFFFFFFFFFull; else
if ((data[7] & 0x80) == 0) value &= 0x00FFFFFFFFFFFFFFull; else
if ((data[8] & 0x80) == 0) value &= 0x7FFFFFFFFFFFFFFFull;
return value;
}
@ugoren: Il n'y a pas. 0x7full == ((non signé long long) 0x7f) .
Vous pouvez même former 0xbull
Tout d'abord, plutôt que de changer, vous pouvez faire un test bit dans le
Bit pertinent. Deuxièmement, vous pouvez utiliser un pointeur plutôt que
Indexation (mais le compilateur devrait faire cette optimisation elle-même.
Ainsi: au moins, cela correspond à ce que fait votre code. Pour variable
Encodage de la longueur des entiers non signés, il est incorrect, car
1) Les codages de longueur variable sont peu d'Endian et votre code est
Big Endian, et 2) Votre code ne doit pas ou dans l'octet élevé.
Enfin, la page Wiki suggère que vous avez le test
inverse. (Je connais ce format principalement de l'encodage BER et
Les tampons de protocole Google, les deux ensemble bit 7 pour indiquer
qu'un autre octet suivra. La routine que j'utilise est la suivante: pour le reste, cela n'a pas été écrit avec des performances à l'esprit, mais
Je doute que vous puissiez faire de manière significative meilleure. Une alternative
la solution serait de prendre d'abord tous les octets, puis
les traiter dans l'ordre inverse: la nécessité de vérifier le dépassement du tampon fera probablement
ce légèrement plus lent, mais sur certaines architectures, changeant de
une constante est significativement plus rapide que de transférer une variable,
Donc, cela pourrait être plus rapide sur eux. globalement, cependant, ne vous attendez pas à des miracles. La motivation pour
en utilisant des entiers de longueur variable consiste à réduire la taille des données, à
un coût en temps d'exécution pour décoder et coder .
Pouvez-vous changer le codage?
Google est tombé sur le même problème et Jeff Dean décrit une solution vraiment cool sur la diapositive 55 de sa présentation:
L'idée de base est que la lecture du premier bit de plusieurs octets est mal soutenue sur les architectures modernes. Au lieu de cela, prenons 8 de ces bits et les emballons comme un octet unique précédant les données. Nous utilisons ensuite l'octet de préfixe pour indiquer dans une table de recherche de 256 éléments, qui contient des masques décrivant comment extraire les nombres du reste des données.
Je crois que c'est la manière dont les tampons de protocole sont actuellement codés.
Pouvez-vous changer votre codage? Comme vous l'avez découvert, en utilisant un peu sur chaque octet pour indiquer s'il y a un autre octet suivant, cueille vraiment pour une efficacité de traitement.
Un meilleur moyen de le faire est de modéliser UTF-8, qui code la longueur de l'intensité complète Le premier octet: p> mais utf-8 a des propriétés spéciales pour faciliter la distinction d'ASCII. Cela corroque les données et vous ne vous souciez pas de l'ASCII, vous le modifiez donc pour ressembler à ceci: p> Ceci a le même niveau de compression que votre méthode (UP à 64 bits = 9 octets), mais est nettement plus facile pour une CPU de traiter. p> à partir de là, vous pouvez créer une table de recherche pour le premier octet qui vous donne un masque et une longueur: P> xxx pré> puis pour décoder: p> // the resulting value.
uint64_t v = 0;
// mask off the data bits in the first byte.
v = *data & byte_masks[*data];
// read in the rest.
switch(byte_counts[*data])
{
case 3: v = v << 8 | *++data;
case 2: v = v << 8 | *++data;
case 1: v = v << 8 | *++data;
case 0: return v;
default:
// If you're on VC++, this'll make it take one less branch.
// Better make sure you've got all the valid inputs covered, though!
__assume(0);
}
Quand je vois v = v << 8 | * ++ données; i Pause et pensez "nécessite plus de parenthèses". Je suis incertain si l'ordre des opérations est correct là-bas.
C'est équivalent à (v << 8) | * ++ Données . Correct, mais peut-être pourrait-il utiliser une parenthèse pour la lisibilité.
Si vous avez un bon compilateur d'optimisation, cela réécrirea probablement cela à toute façon. Dites-lui d'optimiser la vitesse sur ce module, si cela vous sentez généreux, il vous voit probablement aussi pour vous. Vous pouvez également utiliser le mot-clé "Inline" pour informer le compilateur que vous l'appelerez fréquemment et que vous ne voulez pas d'appeler les frais généraux.
@awiebe j'ai peur..my compilateur ne fait pas beaucoup. Même l'astuce suggérée par Ugoren semblait avoir réduit 200 millisecondes. Donc, au cas où une optimisation que vous pourriez suggérer vous aiderait vraiment à m'aider
Je recommande aussi l'utilisation de la lignée en ligne. Mais n'oubliez pas non plus d'activer l'utilisation de l'intégraine dans les paramètres du compilateur et de transformer l'optimisation sur le MAX (par exemple dans MSVC si vous construisez comme débogage, elle n'opisera pas pour des raisons de débogage)
Je suis curieux si ma fonction ci-dessous a réellement aidé beaucoup. Je me rends compte que j'ai légèrement modifier le format de données vers Standard ULEB128. Cela présente des avantages pour le décodage plus rapide, cependant, puisque vous savez toujours lorsque vous atteignez un octet, quels sont les morceaux pour le transférer, quels que soient les autres octets précédents. Et, vous pouvez toujours différer le masquage jusqu'à la fin.
Pourquoi
Func ne présente-t-il pas à quiconque d'octets utilisés? Cette conception nécessite une inefficacité je pense ...Aussi, pourquoi appelez-vous des milliards de fois? C'est à moins quatre terrabytes de données. Harddrives aussi gros sont encore 170 $ +