Question 163

Comment réaliser la concaténation de chaînes de caractères rapidement ?

Lorsque de nombreuses concaténations sont nécessaires, l'opérateur & souffre d'un terrible manque de performances. Nous expliquerons dans cet article la cause du problème et deux solutions possibles pour y remédier.

Il est à remarquer que si la concaténation avec l'opérateur + est possible, elle ne présente aucun gain en performances et n'a pas la sémantique d'une concaténation. Ceci peut mener à des erreurs de compilation ou d'exécution. Dans tous les cas, il s'agit d'un usage déconseillé de l'opérateur +.

Un problème d'allocations

Afin d'expliquer la lenteur d'une concaténation, il est important de déterminer les différentes étapes impliquées dans sa réalisation. La concaténation est réalisée par :

• Une (ré)allocation de mémoire suffisamment importante pour contenir les deux chaînes à concaténer
• La copie des deux chaînes dans la mémoire allouée.

Les allocations mémoire sont des opérations particulièrement lentes. Leur répétition fréquentes entraîne donc nécessairement un impact sur les performances. Le but du jeu consistera donc à minimiser le nombre de ré-allocation, au détriment d'un peu de mémoire allouée de façon supeflue.

Une allocation intelligente de la mémoire

Une solution possible est d'allouer suffisamment de mémoire pour contenir le résultat de l'ensemble des concaténations. Il ne reste alors qu'à réaliser les différentes copies, opération relativement rapide.

Dans la pratique, la taille totale du résultat est généralement inconnue. Il s'agit alors d'allouer une chaîne de caractères "suffisamment grande" et de la redimensionner si nécessaire. On comprend aisément qu'il s'agit de limiter le nombre de ré-allocations et donc que la taille allouée soit supérieure ou égale à la taille du résultat final pour obtenir les meilleures performances.

Voici un exemple d'implémentation de cette technique. La fonction String permettra l'allocation de mémoire et l'instruction Mid$ réalisera la copie de données. Le code suivant est à placer dans un module de classe :

Option Explicit

Private mInternal As String 'Buffer interne
Private mLenB As Long 'Taille en bytes de la chaîne contenue
Private mBlockSize As Long 'Taille en caractères d'un bloc à alouer
Private Const BLOCKSIZE_DEFAULT As Long = 1024

'Accesseurs de propriété pour déterminer la taille d'un bloc à allouer (en caractères)
Public Property Get BlockSize() As Long
    BlockSize = mBlockSize
End Property
Public Property Let BlockSize(Value As Long)
    mBlockSize = Value
End Property

'Effectue une allocation de BlocCount blocs
Public Sub Alloc(BlockCount As Long)
    If (BlockCount > 0) Then
        mInternal = mInternal & String$(mBlockSize * BlockCount, vbNullChar)
    ElseIf (BlockCount < 0) Then
        mInternal = Left$(mInternal, Len(mInternal) + mBlockSize * BlockCount)
    End If
End Sub

'Retourne la chaine de caractères construite
Public Function ToString() As String
    ToString = Left$(mInternal, mLenB / 2)
End Function

'Vide la chaîne de caractère
Public Sub Clear(Optional DeAlloc As Boolean = False)
    mLenB = 0
    If (DeAlloc) Then
        mInternal = vbNullString
    End If
End Sub

'Ajoute la chaine de caractère Text aux données déjà contenues
Public Sub Append(Text As String)
    Dim AllocLength As Long
    AllocLength = (LenB(Text) - (LenB(mInternal) - mLenB)) / 2
    If (AllocLength > 0) Then
        Alloc (AllocLength / mBlockSize + 1)
    End If
    Mid$(mInternal, mLenB / 2 + 1) = Text
    mLenB = mLenB + LenB(Text)
End Sub

'Initialise les différentes variables internes
Private Sub Class_Initialize()
    mLenB = 0
    mBlockSize = BLOCKSIZE_DEFAULT
    mInternal = vbNullString
End Sub

Limiter la mémoire utilisée

Un désavantage de la méthode précédente est que, si la taille est mal évaluée, on peut perdre énormément de place en mémoire. Pour se rapprocher de l'allocation optimale, il faudrait connaître la taille totale du résultat et donc l'ensemble des concaténations à effectuer. Ceci est possible en conservant dans un tableau dynamique — dont la taille sera de préférence allouée par bloc, afin de conserver de bonnes performances malgré la faible perte de mémoire — l'ensemble des chaînes à concaténer.

Voici un exemple d'implémentation de cette technique. Le code suivant est à placer dans un module de classe :

Option Explicit

Private mStrings() As String
Private mArraySize As Long
Private mArrayCapacity As Long

Private mBlockSize As Long 'Taille en nombre de chaines de caractères d'un bloc à alouer
Private Const BLOCKSIZE_DEFAULT As Long = 256

'Accesseurs de propriété pour déterminer la taille d'un bloc à allouer
Public Property Get BlockSize() As Long
    BlockSize = mBlockSize
End Property
Public Property Let BlockSize(Value As Long)
    mBlockSize = Value
End Property

'Effectue une allocation de BlocCount blocs
Public Sub Alloc(BlockCount As Long)
    mArrayCapacity = mArrayCapacity + BlockCount * mBlockSize
    ReDim Preserve mStrings(mArrayCapacity - 1)
End Sub

Private Sub AllocOne()
    mArrayCapacity = mArrayCapacity + mBlockSize
    ReDim Preserve mStrings(mArrayCapacity - 1)
End Sub

'Ajoute la chaine de caractère Text aux données déjà contenues
Public Sub Append(Text As String)
    If mArrayCapacity = mArraySize Then
        AllocOne
    End If
    
    mStrings(mArraySize) = Text
    mArraySize = mArraySize + 1
End Sub

'Retourne la chaine de caractères construite
Public Function ToString() As String
    Dim BufferLength As Long
    Dim TextLength As Long
    Dim BufferPos As Long
    Dim Buffer As String
    Dim i As Long
        
    If mArraySize <> 1 Then
        'Crée un buffer contenant l'ensemble des données
        'et le rempli à l'aide de toutes les chaînes de caractères
        'Si mArraySize = 0, génère une chaîne de caractères vide en
        'mString(0)
        '
        'Remarque: Il est aussi possible d'implémenter ceci avec
        'la méthode Join, sous VB6. Cette méthode n'est pas fournie
        'par le runtime VB5
        
        BufferLength = 0
        BufferPos = 1
        
        For i = 0 To mArraySize - 1
            BufferLength = BufferLength + LenB(mStrings(i))
        Next i
        
        Buffer = String$(BufferLength / 2, vbNullChar)
        
        For i = 0 To mArraySize - 1
            Mid$(Buffer, BufferPos) = mStrings(i)
            BufferPos = BufferPos + Len(mStrings(i))
        Next i
        
        mStrings(0) = Buffer
        mArraySize = 1
    End If
    
    ToString = mStrings(0)
End Function

'Vide la chaîne de caractère
Public Sub Clear(Optional DeAlloc As Boolean = False)
    mArraySize = 0
    If (DeAlloc) Then
        Erase mStrings
    End If
End Sub

Private Sub Class_Initialize()
    mBlockSize = BLOCKSIZE_DEFAULT
    mArraySize = 0
    mArrayCapacity = 0
End Sub

Comparaison des deux méthodes

Nous avons écrit le code précédent de sorte que les appels soient indépendants de la méthode, afin de nous concentrer sur les différences et similitudes réelles. Voici un exemple d'utilisation :

    Dim sb As CStringBuilder
    Dim i As Long

    Set sb = New CStringBuilder
    
    For i = 1 To 50000
        sb.Append "Item" & i & vbCrLf
    Next i
    Debug.Print sb.ToString

Les deux méthodes peuvent présenter des performances déplorables ou excellentes en fonction des valeurs d'allocations et du problème à traiter. Dans la pratique, les deux méthodes seront équivalentes en performances, pour de "bonnes" valeurs de BlockCount. Il est à remarquer que la signification, de même que la valeur, de BlockCount est très différente dans les deux cas.

Les deux méthodes allouent un peu d'espace "inutilement". Néanmoins, sur les systèmes modernes, allouer plus de mémoire que nécessaire n'est pas problématique, particulièrement lorsque de gros volumes de données sont à gérer rapidement. Augmenter les valeurs de blocksize à des valeurs plus hautes que celles proposées par défaut n'est donc pas une mauvaise idée.

Il est important de remarquer que le travail est réalisé à deux endroits très différents entre les méthodes. La première méthode réalise le résultat final au fur et à mesure de nouveaux ajouts. La seconde méthode ne réalise le résultat final que lors de l'appel à ToString. Le résultat généré, dans ce dernier cas, est mis en cache dans le premier élément du tableau. Ceci évite une dégradation des performances lors de plusieurs appels successifs à ToString.

Il serait tentant d'ignorer la première méthode au seul profit de la seconde, vu les performances semblables et l'économie de mémoire. Néanmoins, un point important doit être évoqué, celui de la manipulation de chaînes. La manipulation de chaînes comprend l'extraction d'une partie de la chaîne de caractères, la suppression de caractères en fin, etc. L'implémentation dans le cas de la première méthode est évidente : employer les fonctions internes de VB sur le buffer interne de la classe et/ou manipuler le pointeur de fin de chaîne est entièrement suffisant. Dans le second cas, il est nécessaire de construire complètement la chaîne de caractère, et ensuite appliquer la modification. L'implémentation de telles méthodes peut donc présenter de moins bonnes performances et, de manière générale, est légèrement plus compliquée à réaliser. Ce sont donc les méthodes de manipulation souhaitables et l'occupation mémoire qui dicteront le choix d'une méthode ou d'une autre.

Dans les deux cas, on a des performances nettement meilleures que par la concaténation avec l'opérateur &. Un test, avec des blocksize correctement paramétrés, pour 16000 concaténations, la concaténation par & prenait une minute, contre 60 millisecondes pour un stringbuilder. Cette constatation est générale : des gains situés entre 500 % et 1000 % sont courants.