Какой самый эффективный способ конкатенации строк
Перейти к содержимому

Какой самый эффективный способ конкатенации строк

5 способов конкатенировать строки в Python 3

Конкатенация строк — операция, «склеивающая» несколько строк в одну. Это нельзя назвать особенностью языка, поскольку она присутствует и в PHP, и в Java и много где еще. Для сегодняшнего топа я собрал все способы конкатенации, кроме самых нелепых. Представляю вашему вниманию 5 способов конкатенации строк в Python 3. Сегодня мы рассмотрим варианты множественной конкатенации с применением соединительной строки.

Начнем с проверенной классики — оператора сложения для последовательной конкатенации. Думаю, всем известно, как это работает. Недостаток данного способа — в функции должно быть фиксированное число строк. Вы должны точно знать, сколько в списке строк. Я надумал 2 варианта реализации. Первый — с передачей в аргументы функции всех строк через запятую:

def conc1_1(one, tho, three, four, symbol): return one + symbol + two + symbol + three + symbol + four

Второй — со списком строк в аргументах:

def conc1_2(strings, symbol): return strings[0] + symbol + strings[1] + symbol + strings[2] + symbol + strings[3]

Здесь мы используем строковый метод join(), выполняющий конкатенацию с использованием соединительной строки. Это самое короткий и логичный ответ на такой случай:

def conc2(strings, symbol): return symbol.join(strings)

Если нам не известно количество строк в списке, и почему-то мы не используем метод join() (не могу себе представить такую ситуацию), то этот вариант для нас. Он аналогичен работе метода join()

Как это работает? Присваиваем переменной результата значение первой строки из списка и поочередно конкатенируем к нему соединительный символ и следующие в списке строки, пока не закончится список:

def conc3(strings, symbol): res = strings[0] for i in strings[1::]: res = res + symbol + i return res

Давайте вспомним, что с версии Python 2.6 существует метод format(), предоставляющий возможности форматирования строк. Строки из его аргументов подставляются в исходную строку вместо <>. Поставив рядом две и более пары фигурных скобок, можно соединить 2 и более строк. Аргументы могут быть по умолчанию, а могут быть нумерованными или именованными.

Я написал 2 варианта программы с использованием аргументов по умолчанию и нумерованных:

def conc4_1(strings, symbol): res = strings[0] for i in strings[1::]: res = «<><><>«.format(res, symbol, i) return res

def conc4_2(strings, symbol): res = strings[0] for i in strings[1::]: res = «<0>«.format(res, symbol, i) return res

А здесь напомню про форматирование строк без метода format(), позаимствованное из C (это я прочитал на форуме). Работает оно точно так же, как и встроенный метод, но не позволяет передавать нумерованные и именованные аргументы. В общем вот:

def conc5(strings, symbol): res = strings[0] for i in strings[1::]: res = «%s%s%s» % (res, symbol, i) return res

Примечание: кроме всех указанных способов, я что-то написал. и сам не до конца понял, что я написал. Затем я понял, что накодил чушь. Я проверил, заранее говорю — этот способ самый медленный из всех, поэтому я решил не включать его в основной топ, но все же, вот он:

def conc6(strings, symbol): res = strings[0] list_of_strings = list(strings) for i in range(1, len(strings)): list_of_strings.insert(i + i — 1, symbol) for i in list_of_strings[1::]: res = res + i return res

Статистика быстродействия

Для начала — как измерить время работы программы? Об этом я расскажу в следующей статье. Ну а пока что измерим время работы данного куска кода, где i — одна из шести функций (conc1_2, conc2, conc3, conc4_1, conc4_2, conc5):

Конкатенация строк в Golang

Помимо встроенного оператора + , в Go есть много других способов для конкатенации строк. Далее будет дана простая инструкция для конкатенации, или слияния строк с помощью пакета bytes и встроенной функции copy .

Как конкатенировать строки в Golang?

1. Создайте файл concat_buffer.go со следующим содержимым:

Премиум �� канал по Golang

Рекомендуем вам супер TELEGRAM канал по Golang где собраны все материалы для качественного изучения языка. Удивите всех своими знаниями на собеседовании! ��

Уроки, статьи и Видео

Мы публикуем в паблике ВК и Telegram качественные обучающие материалы для быстрого изучения Go. Подпишитесь на нас в ВК и в Telegram. Поддержите сообщество Go программистов.

concat_buffer.go
package main
strings : = [ ] string < "This " , "is " , "even " , "more " , "performant " >
buffer : = bytes . Buffer < >
for _ , val : = range strings < buffer . WriteString ( val ) fmt . Println ( buffer . String ( ) )

2. Запустите код через go run concat_buffer.go ;
3. Посмотрите на вывод в терминале:

конкатенация строк golang

4. Создайте файл concat_copy.go со следующим содержимым:

concat_copy.go
package main
strings : = [ ] string < "This " , "is " , "even " , "more " , "performant " >
bs : = make ( [ ] byte , 100 )
for _ , val : = range strings < bl += copy ( bs [ bl : ] , [ ] byte ( val ) ) fmt . Println ( string ( bs [ : ] ) )

5. Запустите код через go run concat_copy.go ;
6. Посмотрите на результат в терминале:

конкатенация строк

Код слияния строк в Golang

В шагах 1-3 описывается использование Buffer из пакета bytes в качестве отличного (в плане производительности) решения конкатенации строк. Структура Buffer имплементирует метод WriteString , что может использоваться для эффективной конкатенации строк в базовый байтовый срез.

Нет нужды использовать данное решение во всех случаях. Просто помните о нем, когда программа должна конкатенировать крупное число строк. К примеру, экспорт содержимого большого CSV-файла и прочих.

Встроенная функция copy из шагов 4-6 может использоваться для конкатенации string . Данный метод требует некоторых предположений касательно длины финальной строки, он также может использоваться на ходу. Однако, если вместимость буфера места написания результата меньше уже написанной части и добавленной строки, буфер требуется расширить. Это обычно делается через выделение нового среза с большей вместимостью.

Сравнение способов конкатенации в Golang

Сравним несколько способов конкатенации строк в Golang. Это использование оператора + , bytes.Buffer и встроенной функции copy .

1. Создайте папку bench и файл bench_test.go внутри со следующем содержимым:

Конкатенация строк и производительность

Советы от 5 февраля 2002 «Запись методов toString » (источник и перевод на JavaGu.ru) включали следующее предложение:

Обратите внимание, что использование «+» в toString для построения возвращаемого значения не всегда является самым эффективным подходом. Возможно, вы захотите использовать вместо этого StringBuffer .

Читатель технических советов отметил, что в документации по Java говорится о том, что для фактической реализации оператора + применяется StringBuffer . Поэтому возникает вопрос, какой выигрыш в производительности, если он существует, вы получите при явном использовании StringBuffer в ваших программах? В этой статье делается попытка ответить на этот вопрос.

Для начала рассмотрим пример, в котором строка формируется путем повторения одного и того же символа:

class MyTimer <
private final long start;

public MyTimer () start = System.currentTimeMillis () ;
>

public long getElapsed () return System.currentTimeMillis () — start;
>
>

public class AppDemo1 static final int N = 47500 ;

public static void main ( String args [])

// создать строку при помощи оператора +

MyTimer mt = new MyTimer () ;
String str1 = «» ;
for ( int i = 1 ; i str1 = str1 + «*» ;
>
System.out.println ( «elapsed time #1 = » + mt.getElapsed ()) ;

// создать строку при помощи StringBuffer

mt = new MyTimer () ;
StringBuffer sb = new StringBuffer () ;
for ( int i = 1 ; i sb.append ( «*» ) ;
>
String str2 = sb.toString () ;
System.out.println ( «elapsed time #2 = » + mt.getElapsed ()) ;

// проверка на равенство

if ( !str1.equals ( str2 )) System.out.println ( «str1/str2 mismatch» ) ;
>
>
>

После выполнения этой программы вы должны получить примерно следующий результат:

elapsed time # 1 = 61890
elapsed time # 2 = 16

Подход №2 явно использует StringBuffer , тогда как подход №1 использует его неявно, как часть реализации оператора + . Вы можете исследовать байт-коды, использующиеся для реализации первого подхода при помощи команды:

javap -c -classpath . AppDemo1

Разница в «+» и StringBuffer

Откуда такая огромная разница между этими двумя подходами? Во втором подходе символы добавляются в StringBuffer , что довольно эффективно. А в первом подходе не используется этот метод? На самом деле нет. Выражение:

str1 = str1 + «*» ;

не добавляет символы к строке str1 . Это происходит из-за того, что Java-строки постоянны, они не изменяются после создания. Вот что происходит в действительности:

  • StringBuffer создается
  • str1 копируется в него
  • «*» добавляется в буфер
  • Результат преобразуется в строку
  • Ссылка str1 меняется для указания на эту строку
  • Старая строка, на которую ранее ссылалась переменная str1 , делается доступной для сборщика мусора.

Цикл проходит через N итераций, и на каждой итерации содержимое str1 (содержащей N-1 символов) должно быть скопировано в буфер. Такое поведение подразумевает, что первый подход имеет квадратичную или худшую производительность. «Квадратичная» означает, что время выполнения пропорционально квадрату N. Есть вероятность эффективно заморозить приложение при применении такого типа цикла.

В примере AppDemo1 демонстрируется ситуация, когда периодически присоединяется одна строка к другой, так что обе строки должны быть скопированы во временную область ( StringBuffer ), создана новая строка и, затем, ссылка на оригинальную строку заменяется ссылкой на новую строку.

Но что если вы не выполняете этот тип операции, а вместо этого, просто имеете некоторый код, похожий на следующий:

public String toString () <
return «X=» + x + » Y=» + y;
>

Здесь нет цикла или повторений и нет строки, которая становится все длиннее и длиннее. Есть какой-либо вред от применения + вместо StringBuffer в этом примере?

Поясняющий пример

В примере AppDemo1 демонстрируется ситуация, когда периодически присоединяется одна строка к другой, так что обе строки должны быть скопированы во временную область ( StringBuffer ), создана новая строка и, затем, ссылка на оригинальную строку заменяется ссылкой на новую строку.

Но что если вы не выполняете этот тип операции, а вместо этого, просто имеете некоторый код, похожий на следующий:

public String toString () <
return «X=» + x + » Y=» + y;
>

Здесь нет цикла или повторений и нет строки, которая становится все длиннее и длиннее. Есть какой-либо вред от применения + вместо StringBuffer в этом примере?

Для ответа на этот вопрос рассмотрим дополнительный код:

class MyPoint <
private final int x, y;
private final String cache;

public MyPoint ( int x, int y ) this .x = x;
this .y = y;
cache = «X=» + x + » Y=» + y;
>

public String toString1 () return «X=» + x + » Y=» + y;
>

public String toString2 () StringBuffer sb = new StringBuffer () ;
sb.append ( «X=» ) ;
sb.append ( x ) ;
sb.append ( » Y=» ) ;
sb.append ( y ) ;
return sb.toString () ;
>

public String toString3 () String s = «» ;
s = s + «X=» ;
s = s + x;
s = s + » Y=» ;
s = s + y;
return s;
>

public String toString4 () return cache;
>
>

class MyTimer private final long start;

public MyTimer () start = System.currentTimeMillis () ;
>

public long getElapsed () return System.currentTimeMillis () — start;
>
>

public class AppDemo2 static final int N = 1000000 ;

public static void main ( String args []) MyPoint mp = new MyPoint ( 37 , 47 ) ;
String s1 = null ;
String s2 = null ;
String s3 = null ;
String s4 = null ;

MyTimer mt = new MyTimer () ;
for ( int i = 1 ; i s1 = mp.toString1 () ;
>
System.out.println ( «toString1 » + mt.getElapsed ()) ;

mt = new MyTimer () ;
for ( int i = 1 ; i s2 = mp.toString2 () ;
>
System.out.println ( «toString2 » + mt.getElapsed ()) ;

mt = new MyTimer () ;
for ( int i = 1 ; i s3 = mp.toString3 () ;
>
System.out.println ( «toString3 » + mt.getElapsed ()) ;

mt = new MyTimer () ;
for ( int i = 1 ; i s4 = mp.toString4 () ;
>
System.out.println ( «toString4 » + mt.getElapsed ()) ;

// проверка исправности для того, чтобы убедиться,
// что результаты, возвращенные из каждого метода toString идентичны

if ( !s1.equals ( s2 ) || !s2.equals ( s3 ) || !s3.equals ( s4 )) System.out.println ( «check error» ) ;
>
>
>

В этой программе создается класс MyPoint , который используется для представления точек X,Y . В ней реализуются различные методы toString для класса. Результат выполнения программы может выглядеть примерно так:

toString1 2797
toString2 2703
toString3 5656
toString4 32

Расшифровка результатов

Первые два способа, использующие + и StringBuffer , имеют примерно одинаковую производительность. Поэтому вы можете сделать вывод, что эти два способа фактически идентичны. Генерируемый для toString1 байт-код указывает, что создается StringBuffer , а затем различные строки просто добавляются к нему. Полученный код очень похож на toString2 .

Но не все так просто. Первая проблема в том, что вы не всегда сможете сформулировать возвращаемое из toString значение в виде отдельного выражения. toString3 и toString1 показывают идентичные результаты. Но время работы toString3 в два раза больше по причине, описанной в примере AppDemo1 . Пример AppDemo2 демонстрирует ситуацию, когда надо создать возвращаемое значение за один раз. В этом случае toString2 , использующий явно StringBuffer , является более хорошим выбором.

Другая проблема касается высказывания, найденного в «Спецификации по языку программирования Java» в разделе 15.18.1.2, в котором говорится:

Реализация может выполнить преобразование и конкатенацию за один шаг, чтобы избежать создания и удаления промежуточного объекта String . Для увеличения производительности повторных конкатенаций строки компилятор Java может использовать класс StringBuffer или аналогичную технику для уменьшения количества промежуточных объектов String , создающихся при вычислении выражения.

Это утверждение говорит о том, что компилятор Java не обязательно оптимизирует такое выражение как:

str1 + str2 + str3 + .

как это сделано для метода toString1 , а может вместо этого создать промежуточные строковые объекты.

Поэтому будьте осторожны при использовании оператора + , особенно для длинных строк или в циклах.

Отметим, что существует даже более быстрый способ реализации toString для этого примера. MyPoint является постоянным классом. Это означает, что его экземпляры не могут быть модифицированы после создания. Учитывая это, возвращаемое из toString значение всегда будет одним и тем же. Поскольку значения одинаковы, оно может быть вычислено один раз в конструкторе MyPoint и затем просто возвращено из toString4 .

Такой вид кэширования часто очень полезен, но есть и отрицательные стороны. Если класс является изменяемым, то кэширование может не иметь смысла. Тоже самое можно сказать и для ситуаций, когда вычисление значения кэша трудоемко, когда кэш занимает много памяти, или когда метод toString вызывается нечасто.

Ссылки

Дополнительная информация по этой теме находится в разделе 15.18.1 «Оператор конкатенации строк +» в «Спецификации по языку программирования Java, второе издание (http://java.sun.com/docs/books/jls/), и в разделе 5 «Строки» книги «Настройка производительности Java» Jack Shirazi.

A может Вас также заинтересует что-нибудь из этого:
  1. Разное → Теория и практика Java: Динамическая компиляция и измерение производительности
  2. Java сниппеты → Какой длины ваша строка?
  3. Java Standard Edition → Блокировки
  4. Java сниппеты → Блоки статической и объектной инициализации
  5. Java сниппеты → Методы для работы с переменным количеством аргументов
  6. Java Standard Edition → Производительность операций ввода/вывода в Java

Ускорение конкатенации строк в Go своими руками

Сегодня мы будем разгонять склеивание коротких строк в Go на 30%. Причём для этого нам не нужно будет модифицировать сам Go, всё это будет реализованно в виде сторонней библиотеки.

Под катом вас ждут:

  • Сравнение + , strings.Builder и собственной функции конкатенации
  • Детали внутреннего устройства строк в Go
  • Совсем немного ассемблера

Данную статью можно также считать предлогом обсудить CL123256: runtime,cmd/compile: specialize concatstring2. Идеи по улучшению этого change list’а приветствуются.

Сразу результаты

Сравнение производилось с go tip (master) версией компилятора. Аналогичные результаты вы можете получить на версиях примерно с Go 1.5. Последним значительным изменением функции concatstrings был CL3120: cmd/gc: allocate buffers for non-escaped strings on stack.

BenchmarkConcat2Operator-8 20000000 83.8 ns/op BenchmarkConcat2Builder-8 20000000 70.9 ns/op BenchmarkConcat2-8 20000000 62.1 ns/op BenchmarkConcat3Operator-8 20000000 104 ns/op BenchmarkConcat3Builder-8 20000000 89.9 ns/op BenchmarkConcat3-8 20000000 82.1 ns/op

ConcatOperator использует + .
ConcatBuilder использует strings.Builder с правильной пред-аллокацией.
Concat использует функцию, которую мы реализуем в рамках этой истории.

name old time/op new time/op delta Concat2-8 84.2ns ± 1% 62.7ns ± 2% -25.49% (p=0.000 n=9+10) Concat3-8 103ns ± 3% 83ns ± 4% -19.83% (p=0.000 n=10+9)

Ассемблерная реализация под GOARCH=AMD64 немного быстрее и обладает дополнительной оптимизацией, которая присутствует у встроенного оператора + , но об этом ниже:

name old time/op new time/op delta Concat2-8 84.2ns ± 1% 57.1ns ± 3% -32.20% (p=0.000 n=9+9)

Ассемблерную функцию будем брать как 100% производительности (относительно остальных рассматриваемых реализаций).

Результаты для более длинных строк можно увидеть в README.md. Чем длиннее строка, тем менее выражена разница между реализациями.

Наивная конкатенация

Самым простым решением является использование оператора + .

Семантика этого оператора такая: взять две строки и вернуть строку-результат, которая содержит сцепление обеих строк. При этом нет гарантии, что будет возвращена новая строка. Например, если происходит сцепление пустой строки и любой другой, runtime может вернуть непустой аргумент, избегая необходимости выделять новую память и копировать туда данные.

Но, как видно из результатов в начале статьи, это самый медленный способ.

func concat2operator(x, y string) string

Оценка производительности: 67.8%.

strings.Builder

Не так давно в Go добавили новый тип — strings.Builder. Это аналог bytes.Buffer , но при вызове метода String() не происходит повторного выделения памяти и копирования данных.

В отличие от bytes.Buffer , builder не имеет оптимизации малого буфера и, следовательно, предварительно аллоцированной памяти под строку. Если не использовать метод Grow , производительность будет хуже, чем в случае с bytes.Buffer . Несколько регрессий в Go 1.11 вызваны именно этой особенностью (см. CL113235).

В нашем коде, для чистоты эксперимента, мы будем избегать этой ошибки.

func concat2builder(x, y string) string < var builder strings.Builder builder.Grow(len(x) + len(y)) // Только эта строка выделяет память builder.WriteString(x) builder.WriteString(y) return builder.String() >

Оценка производительности: 80.5% (+12.7).

Кодогенерация для конкатенации

Если посмотреть, какой код генерирует компилятор для оператора + , мы увидим вызовы функций concatstring2 , concatstring3 и так далее (до concatstring5 включительно).

func concat2codegen(x, y) string < return x + y >// => CALL runtime.concatstring2(SB) func concat3codegen(x, y, z) string < return x + y + z >// => CALL runtime.concatstring3(SB)
func concatstring2(buf *tmpBuf, a [2]string) string < return concatstrings(buf, a[:]) >func concatstring3(buf *tmpBuf, a [3]string) string

Значит, осталось изучить функцию concatstrings .
Полный листинг доступен ниже под спойлером, а вот высокоуровневое описание:

  1. Параметр buf может быть nil . Этот буфер выделяется компилятором, если строка не «убегает» из области своего определения. Если же строка живёт дольше, чем фрейм, то этот буфер всегда будет nil (как чаще всего и происходит). Однако если этот буфер доступен, получится избежать аллокации в случае, если результат в него влезает (его размер — 32 байта).
  2. Если все строки, кроме одной, пустые, функция вернёт эту строку. Но при этом выделенные на стеке и покидающие свой фрейм строки минуют этой оптимизации, чтобы вызывающая сторона не получила уже освобождённую память.
  3. Далее все строки копируются в новую память.

Полный листинг функции concatstrings

// concatstrings implements a Go string concatenation x+y+z+. // The operands are passed in the slice a. // If buf != nil, the compiler has determined that the result does not // escape the calling function, so the string data can be stored in buf // if small enough. func concatstrings(buf *tmpBuf, a []string) string < idx := 0 l := 0 count := 0 for i, x := range a < n := len(x) if n == 0 < continue >if l+n < l < throw("string concatenation too long") >l += n count++ idx = i > if count == 0 < return "" >// If there is just one string and either it is not on the stack // or our result does not escape the calling frame (buf != nil), // then we can return that string directly. if count == 1 && (buf != nil || !stringDataOnStack(a[idx])) < return a[idx] >s, b := rawstringtmp(buf, l) for _, x := range a < copy(b, x) b = b[len(x):] >return s >

Здесь мы видим сразу несколько мест, которые могут быть оптимизированы для частного случая:

  • buf чаще всего пустой. Когда компилятор не смог доказать, что строку безопасно размещать на стеке, передача лишнего параметра и проверка его на nil внутри функции дают лишь накладные расходы.
  • Для частного случая при len(a) == 2 нам не нужен цикл и вычисления можно упростить. А это самый распространённый вид конкатенации.

Статистика по использованию конкатенации

При выполнении ./make.bash (сборка Go компилятора и stdlib) видим 445 конкатенаций с двумя операндами:

  • 398 результатов «убегают». В этом случае наша специализация имеет смысл.
  • 47 результатов не покидают своего фрейма.

Итого 89% конкатенаций от двух аргументов попадают пот оптимизацию.

Для утилиты go имеем:

  • 501 вызовов concatstring2
  • 194 вызовов concatstring3
  • 55 вызовов concatstring4

Версия для всех архитектур

Для реализации специализации нам потребуется знать, как в Go представлены строки. Нам важна бинарная совместимость, при этом unsafe.Pointer можно заменить на *byte без каких-либо жертв.

type stringStruct struct

Второй важный вывод, который мы можем сделать из рантайма: строки начинают свою жизнь мутабельными. Выделяется участок памяти, на который ссылается []byte , в который записывается содержимое новой строки, и только после этого []byte выбрасывается, а память, на которую он ссылался, сохраняется в stringStruct .

Для тех, кому хочется больше деталей, предлагается изучить функции rawstringtmp и rawstring .

runtime.rawstring

// rawstring allocates storage for a new string. The returned // string and byte slice both refer to the same storage. // The storage is not zeroed. Callers should use // b to set the string contents and then drop b. func rawstring(size int) (s string, b []byte) < p := mallocgc(uintptr(size), nil, false) stringStructOf(&s).str = p stringStructOf(&s).len = size *(*slice)(unsafe.Pointer(&b)) = slicereturn >

Мы можем провернуть примерно то же самое, воспользовавшись тёмной стороной пакета unsafe :

func concat2(x, y string) string < length := len(x) + len(y) if length == 0 < return "" >b := make([]byte, length) copy(b, x) copy(b[len(x):], y) return goString(&b[0], length) >

Мы выделяем []byte , который используем для формирования содержимого новой строки. Затем нам остаётся лишь финализировать строку приведением её к ожидаемому рантаймом представлению. За это отвечает функция goString :

func goString(ptr *byte, length int) string < s := stringStructreturn *(*string)(unsafe.Pointer(&s)) >

Оценка производительности: 91.9% (+10.9).

Версия для AMD64

К сожалению, предыдущая версия функции не имеет оптимизации для конкатенации с пустой строкой, а ещё мы выполняем некоторое количество лишних вычислений из-за невозможности выделить память напрямую, приходится работать со слайсом байт.

Одной из интересных особенностей Go ассемблера является то, что он позволяет вызывать, например, неэкспортируемые функции рантайма. Мы можем вызвать runtime·mallocgc из ассемблерного кода даже если он не является частью пакета runtime . Этим свойством мы и воспользуемся.

Также мы можем проверять принадлежность строк стековой памяти, что делает безопасной оптимизацию возврата одного из аргументов в качестве результата.

Допустим, функция вызвана с аргументами concat2(«», «123») . x — пустая строка, и если y не выделен на стеке, мы можем вернуть его в качестве результата конкатенации.

//; Считаем, что x и y имеют тип stringStruct. //; CX - y.str. //; SI - y.len. maybe_return_y: //; Проверка на вхождения указателя в стек. MOVQ (TLS), AX //; *g CMPQ CX, (AX) JL return_y //; если y_str < g.stack.lo CMPQ CX, 8(AX) JGE return_y //; если y_str >= g.stack.hi JMP concatenate //; y на стеке, нужна новая аллокация return_y: MOVQ CX, ret+32(FP) //; stringStruct.len MOVQ SI, ret+40(FP) //; stringStruct.str RET

MOVQ (TLS), AX переместит *g в регистр AX . Чтение по нулевому смещению даст поле g.stack.lo , а с 8-го байта начинается g.stack.hi (для 64-битной платформы).

type g struct < stack struct < lo uintptr // 0(AX) hi uintptr // 8(AX) >stackguard0 uintptr // 16(AX) stackguard1 uintptr // 24(AX) // . другие поля >

Тело concatenate выделяет память, заполняет его обеими строками, и возвращает новую строку.

Полный листинг с комментариями

#include "textflag.h" #include "funcdata.h" TEXT ·Strings(SB), 0, $48-48 NO_LOCAL_POINTERS // Костыль для избежания ошибки. MOVQ x+0(FP), DX MOVQ x+8(FP), DI MOVQ y+16(FP), CX MOVQ y+24(FP), SI TESTQ DI, DI JZ maybe_return_y // x - пустая строка, попробуем вернуть y TESTQ SI, SI JZ maybe_return_x // y - пустая строка, попробуем вернуть x concatenate: LEAQ (DI)(SI*1), R8 // len(x) + len(y) // Выделяем память для новой строки. MOVQ R8, 0(SP) MOVQ $0, 8(SP) MOVB $0, 16(SP) CALL runtime·mallocgc(SB) MOVQ 24(SP), AX // Указатель на выделенную память MOVQ AX, newstr-8(SP) // Копируем x. MOVQ x+0(FP), DX MOVQ x+8(FP), DI MOVQ AX, 0(SP) MOVQ DX, 8(SP) MOVQ DI, 16(SP) CALL runtime·memmove(SB) // Копируем y со смещения len(x). MOVQ x+8(FP), DI MOVQ y+16(FP), CX MOVQ y+24(FP), SI MOVQ newstr-8(SP), AX LEAQ (AX)(DI*1), BX MOVQ BX, 0(SP) MOVQ CX, 8(SP) MOVQ SI, 16(SP) CALL runtime·memmove(SB) // Возврат новой строки. MOVQ newstr-8(SP), AX MOVQ x+8(FP), R8 ADDQ y+24(FP), R8 MOVQ AX, ret+32(FP) MOVQ R8, ret+40(FP) RET maybe_return_y: // Проверка на вхождения указателя в стек. MOVQ (TLS), AX // *g CMPQ CX, (AX) JL return_y // если y_ptr < stk.lo CMPQ CX, 8(AX) JGE return_y // если y_ptr >= stk.hi JMP concatenate // y на стеке, нужна новая аллокация return_y: MOVQ CX, ret+32(FP) MOVQ SI, ret+40(FP) RET maybe_return_x: // Проверка на вхождения указателя в стек. MOVQ (TLS), AX // *g CMPQ DX, (AX) JL return_x // если x_ptr < stk.lo CMPQ DX, 8(AX) JGE return_x // если x_ptr >= stk.hi JMP concatenate // x на стеке, нужна новая аллокация return_x: MOVQ DX, ret+32(FP) MOVQ DI, ret+40(FP) RET

Если вам интересна природа NO_LOCAL_POINTERS в этом коде, можете почитать Calling a Go function from asm («fatal error: missing stackmap»).

Оценка производительности: 100% (+8.6).

В качестве заключения

Весь код предоставлен в качестве пакета concat.

Готов ли мир к такой быстрой конкатенации? Who knows.

В начале статьи был упомянут CL123256. У него есть несколько путей развития:

  1. Вариадичная специализация для случая, когда компилятором не выделен временный буфер. Меньше прирост на каждый случай, зато покрывает больше видов конкатенации и практически не увеличивает размер кода (как машинного, так и кода на Go).
  2. Больше специализаций для частных случаев. Выше прирост, но больше машинного кода, может навредить кешу инструкций.
  3. Тонны машинного кода, для каждого особого случая и специализированный memmove, на манер того как это сделано в glibc. Здесь в основном встают вопросы целесообразности.

Текущий предложенный вариант ускоряет только наиболее частый и простой случай конкатенации пары строк (арность=2).

Если в Go не примут это изменение, то сравнимого ускорения можно будет добиться с помощью реализации операций над строками в виде сторонней библиотеки. Менее удобно, красиво и элегантно, но зато работает.

  • Программирование
  • Assembler
  • Системное программирование
  • Компиляторы
  • Go

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *