Introduit un algorithme qui calcule le nombre de points de code à partir d'une chaîne UTF-8. Le comptage des points de code n'est pas trop difficile à écrire simplement, mais son implémentation hautement efficace est étonnamment déroutante.
Le contenu est à double canon.
--Pour une mise en œuvre pratique, je présenterai celui utilisé dans l'implémentation interne (string.c) de Ruby (CRuby). --Au-delà de la gamme C standard, nous décrirons également l'implémentation à l'aide d'instructions SIMD (AVX / AVX2). «Je n'ai pas pu trouver un algorithme connu dans la mesure où j'ai cherché à la légère, j'ai donc déformé une implémentation ad hoc, mais il semble que ce ne soit pas si inefficace.
En prime, j'ai essayé une simple évaluation des performances. On suppose que la chaîne UTF-8 a été validée (on sait qu'il ne s'agit pas d'une séquence invalide).
Tout d'abord, définissez ʻis_utf8_lead_byte` pour déterminer s'il s'agit du premier octet du point de code. C'est une macro de préprocesseur.
#define is_utf8_lead_byte(c) (((c)&0xC0) != 0x80)
https://github.com/ruby/ruby/blob/v2_6_2/string.c#L1629
Le masquage de «0xC0» ou «0b11000000» ne laisse que les deux premiers bits. Puisque le non-premier octet de UTF-8 est dans l'ordre de «0b10xxxxxx», s'il s'agit d'un non-premier octet, ce sera «0b10000000» après le masquage, mais cela signifie que l'opération de comparaison «! = 0x80» détermine s'il s'agit du premier octet. Cela signifie que vous pouvez.
Cette macro facilite la mise en œuvre du comptage des points de code.
#define is_utf8_lead_byte(c) (((c)&0xC0) != 0x80)
int64_t count_utf8_codepoint(const char *p, const char *e) {
while (p < e) {
if (is_utf8_lead_byte(*p)) len++;
p++;
}
return len;
}
Au fait, c'est simple jusqu'à présent, mais l'implémentation dans le système de traitement Ruby a été conçue un peu plus. Dans l'implémentation simple ci-dessus, le traitement des chaînes de caractères est effectué en unités d'octets, mais dans un environnement typique tel qu'un PC / serveur moderne, les entiers 32/64 bits peuvent être traités sans aucun inconvénient, de sorte que le traitement de chaque octet est possible. C'est relativement inefficace. Par conséquent, plusieurs octets sont lus ensemble dans le type ʻuintptr_t`, et le nombre de tous les premiers octets inclus est compté à la fois. ** Le nombre de points de code est égal au nombre de premiers octets **, il vous suffit donc de compter les premiers octets pour compter les points de code.
#define NONASCII_MASK UINT64_C(0x8080808080808080)
static inline uintptr_t
count_utf8_lead_bytes_with_word(const uintptr_t *s)
{
uintptr_t d = *s;
d = (d>>6) | (~d>>7);
d &= NONASCII_MASK >> 7;
return __builtin_popcountll(d);
}
https://github.com/ruby/ruby/blob/v2_6_2/string.c#L1631-L1665
sizeof (uintptr_t) == 8.C'est un peu déroutant car il est calculé tous ensemble, mais veuillez noter les points suivants.
--NONASCII_MASK >> 7 est un masque dans lequel seul le bit le moins significatif de chaque octet est défini.
-- d est un bit et avec ceci, il ne reste donc que le bit le moins significatif
--Lorsque vous vous concentrez sur le bit le moins significatif de chaque octet de (d >> 6) | (~ d >> 7), il est jugé que "le 7ème bit est haut ou le 8ème bit est bas".
――Le 7ème bit ressort: rappelez-vous que le non-premier octet de UTF-8 est toujours dans l'ordre «0b10xxxxxx», c'est-à-dire le premier octet.
--Le 8e bit est manquant: puisqu'il s'agit de l'ASCII, le
Après l'opération sur les bits, «d» indiquera qu'il s'agit du premier octet si le bit le moins significatif est défini pour chaque octet. Les autres bits sont masqués et sont toujours à 0. Par conséquent, pour compter le nombre de premiers octets inclus, vous pouvez faire popcnt.
Enfin, enfin, je vais vous donner un aperçu de l'implémentation en utilisant count_utf8_lead_bytes_with_word.
int64_t ruby_count_utf8_codepoint(const char *p, const char *e)
{
uintptr_t len = 0;
if ((int)sizeof(uintptr_t) * 2 < e - p) {
const uintptr_t *s, *t;
const uintptr_t lowbits = sizeof(uintptr_t) - 1;
s = (const uintptr_t*)(~lowbits & ((uintptr_t)p + lowbits));
t = (const uintptr_t*)(~lowbits & (uintptr_t)e);
while (p < (const char *)s) {
if (is_utf8_lead_byte(*p)) len++;
p++;
}
while (s < t) {
len += count_utf8_lead_bytes_with_word(s);
s++;
}
p = (const char *)s;
}
while (p < e) {
if (is_utf8_lead_byte(*p)) len++;
p++;
}
return (long)len;
}
https://github.com/ruby/ruby/blob/v2_6_2/string.c#L1680-L1700
Je parle de la raison pour laquelle c'est une implémentation si compliquée, mais pour que count_utf8_lead_bytes_with_word fonctionne correctement, un pointeur aligné sur la limite de n octets de ʻuintptr_t` (typiquement je pense n = 4 ou 8). Parce qu'il a besoin d'être lu. La méthode spécifique est la suivante.
lowbits puis en masquant, avancep jusqu'à la position alignée et fais-la s.Vous pouvez utiliser count_utf8_lead_bytes_with_word pour les pré-traitéss et t.
Bien sûr, il peut y avoir un écart entre «s», «t» et «p», «e», donc nous utilisons un traitement de boucle normal pour combler les différences avant et après.
(Ajouté le 18/04/2019) @umezawatakeshi a amélioré l'implémentation ici. Si vous souhaitez implémenter AVX, veuillez également vous reporter à cet article. https://qiita.com/umezawatakeshi/items/ed23935788756c800b86
Ce n'est pas un algorithme, je vais donc l'expliquer en parallèle avec l'implémentation.
Comme politique de base, comme UTF-8 Validation Algorithm, nous utilisons la propriété qui vous permet de dire si c'est le premier octet en regardant le quartet supérieur de l'octet. .. Vous pouvez utiliser vpshufb pour définir 1 uniquement à la position où se trouvait le premier octet. Bien que ce soit une façon de compter 1, il est coûteux d'ajouter dans le sens horizontal dans SIMD, nous allons donc ajouter les vecteurs découpés en unités de 32 octets tels quels. Cependant, étant donné que la plage de valeurs pouvant être représentées par des octets est comprise entre 0 et 255, un dépassement de capacité peut se produire si l'ajout de vecteurs est effectué plus de 255 fois. La solution de contournement consiste à fractionner la boucle et à agréger les valeurs par addition horizontale toutes les 255 fois (bien sûr, s'il n'y a plus d'entrées, la boucle se terminera avant 255 fois). Si vous faites cela, l'ajout horizontal ne sera effectué qu'une seule fois au minimum et une fois toutes les 255 fois au maximum, vous pouvez donc vous attendre à un coût relativement faible.
Maintenant, c'est la mise en œuvre. Tout d'abord, définissez une fonction qui ajoute horizontalement en unités d'octets en tant que fonction auxiliaire.
inline int32_t avx2_horizontal_sum_epi8(__m256i x)
{
__m256i sumhi = _mm256_unpackhi_epi8(x, _mm256_setzero_si256());
__m256i sumlo = _mm256_unpacklo_epi8(x, _mm256_setzero_si256());
__m256i sum16x16 = _mm256_add_epi16(sumhi, sumlo);
__m256i sum16x8 = _mm256_add_epi16(sum16x16, _mm256_permute2x128_si256(sum16x16, sum16x16, 1));
__m256i sum16x4 = _mm256_add_epi16(sum16x8, _mm256_shuffle_epi32(sum16x8, _MM_SHUFFLE(0, 0, 2, 3)));
uint64_t tmp = _mm256_extract_epi64(sum16x4, 0);
int32_t result = 0;
result += (tmp >> 0 ) & 0xffff;
result += (tmp >> 16) & 0xffff;
result += (tmp >> 32) & 0xffff;
result += (tmp >> 48) & 0xffff;
return result;
}
En utilisant ʻavx2_horizontal_sum_epi8`, il est relativement facile d'écrire une fonction qui compte les points de code pour des multiples de 32.
int64_t avx_count_utf8_codepoint(const char *p, const char *e)
{
// `p` must be 32B-aligned pointer
p = static_cast<const char *>(__builtin_assume_aligned(p, 32));
const size_t size = e - p;
int64_t result = 0;
for (size_t i = 0; i + 31 < size;) {
__m256i sum = _mm256_setzero_si256();
size_t j = 0;
for (; j < 255 * 32 && (i + 31) + j < size; j += 32) {
const __m256i table = _mm256_setr_epi8(
1, 1, 1, 1, 1, 1, 1, 1, // .. 0x7
0, 0, 0, 0, // 0x8 .. 0xB
1, 1, 1, 1, // 0xC .. 0xF
1, 1, 1, 1, 1, 1, 1, 1, // .. 0x7
0, 0, 0, 0, // 0x8 .. 0xB
1, 1, 1, 1 // 0xC .. 0xF
);
__m256i s = _mm256_load_si256(reinterpret_cast<const __m256i *>(p + i + j));
s = _mm256_and_si256(_mm256_srli_epi16(s, 4), _mm256_set1_epi8(0x0F));
s = _mm256_shuffle_epi8(table, s);
sum = _mm256_add_epi8(sum, s);
}
i += j;
result += avx2_horizontal_sum_epi8(sum);
}
return result;
}
La boucle interne ajoute chaque vecteur et la boucle externe agrège les valeurs d'élément du vecteur ajouté et les ajoute au «résultat».
table est une table de conversion pour détecter le premier octet du quartet supérieur de UTF-8 et définir uniquement le premier octet à 1.
L'expression conditionnelle «j <255 * 32 && (i + 31) + j <size» pour la boucle interne est un peu déroutante. La variable de boucle «j» est incrémentée de 32, donc la première moitié de l'expression conditionnelle «j <255 * 32» signifie que la boucle est interrompue à 255 fois. La seconde moitié, (i + 31) + j <size, est une protection pour empêcher la longueur d'entrée size de dépasser un multiple de 32. Lorsque la boucle interne se termine, «j» est ajouté à «i», donc «i + 31 <size» de la boucle externe devient également 0, et la boucle se termine.
La partie qui s'étend au-delà du multiple de 32 peut être combinée avec l'implémentation Ruby. Cette fois, j'ai essayé de remplir la partie saillante avec une implémentation qui traite un octet à la fois. Puisqu'il est possible que «p» ne soit pas aligné avec la limite 32B, j'ai également inséré un processus pour avancer par scalaire jusqu'à la limite 32B avant le traitement vectoriel.
_ * (Ajouté le 07/04/2019 00:30) Le code a été corrigé car il y avait un bug. _
int64_t count_utf8_codepoint(const char *p, const char *e)
{
int64_t count = 0;
#if defined(__AVX2__)
if (32 <= e - p) {
// increment `p` to 32B boundary
while (((uintptr_t)p % 32) != 0) {
if (is_utf8_lead_byte(*p)) count++;
p++;
}
// vectorized count
count += avx_count_utf8_codepoint(p, e);
p += static_cast<uintptr_t>(e - p) / 32 * 32;
}
#endif
while (p < e) {
if (is_utf8_lead_byte(*p)) count++;
p++;
}
return count;
}
Cette fois, nous examinerons si le débit est suffisant pour les longues chaînes et dans quelle mesure il est quantitatif.
Je décrirai brièvement les conditions d'évaluation des performances.
--Environnement: Ubuntu 18.04.1 sur VirtualBox sur MBP fin 2013
-O3 -masm = intel --std = c ++ 14 -mavx -mavx2 -Wall -WextraLes cibles de mesure sont la version scalaire introduite, la version Ruby et le count_utf8_codepoint (ci-après dénommé la version AVX) décrit dans la section sur l'implémentation de la collaboration.
| la mise en oeuvre | compilateur | Nombre de cycles d'horloge(Mclk) |
|---|---|---|
| Version scalaire | GCC | 7323 |
| Version scalaire | Clang | 8793 |
| Version rubis | GCC | 4573 |
| Version rubis | Clang | 2643 |
| Version AVX | GCC | 2361 |
| Version AVX | Clang | 2345 |
Le résultat global est que la version scalaire est la plus lente et la version AVX est la plus rapide.
L'implémentation Ruby a une grande différence entre GCC et Clang, ce qui semble être dû au bon fonctionnement de la vectorisation automatique de Clang.
La vectorisation automatique de GCC ne fonctionne pas pour la partie la plus lourde de la version Ruby (la boucle de while (s <t)), où il y a une grande différence.
Fait intéressant, GCC semble être plus efficace pour la génération de code lorsque la version scalaire est auto-vectorisée. Clang a-t-il obtenu un indice de la version Ruby de l'algorithme ... J'espère que ce n'est pas une erreur de mesure.
En comparant la version Ruby et la version AVX pour le même système de traitement (Clang), la vitesse peut être augmentée d'environ 10% en écrivant à la main le code AVX. Cependant, avec le support du compilateur, on peut dire qu'environ 90% des performances de l'écriture manuscrite intrinsèque ont été obtenues relativement facilement, il semble donc que le problème des performances de coût est susceptible de se poser.
À propos, en temps réel, la version AVX-Clang était d'environ 0,838 secondes. En d'autres termes, environ 12 Gio / s sont sortis. Étant donné que la chaîne de caractères est suffisamment grande, le cache ne fonctionne pas, et étant donné que la mémoire DDR3-1600 2ch attachée à ce MBP a une bande théorique de 25,6 Gio / s, environ 50% de la bande peut être utilisée. Devenir. Je pense que c'est plus que suffisant pour un programme à un seul thread.
Appendix
https://gist.github.com/saka1/5bdd0f0ad4e498d22258982f6b9699c5
Recommended Posts