О быстродействии Basic

[sokol92]

OK. Сделаю, но не сразу, заодно измерим температуру еще одной кузине (REPLACE).

[mikekaganski]

заодно измерим температуру еще одной кузине (REPLACE)

Ну, эта не проблемная (хотя и её можно ускорить). А вот, например,

Код Выделить Развернуть

=CLEAN(REPT(CHAR(9);1000000))

тоже повиснет надолго. CLEAN почти такой же тормоз, как и SUBSTITUTE. И вообще у нас полно мест, где мы используем подобного рода замены (replaceAt).

[sokol92]

Михаил, большое спасибо! Результаты расследования опубликуем здесь.

[sokol92]

CLEAN почти такой же тормоз, как и SUBSTITUTE.

CLEAN лечится классическим математическим приемом. Меняем непечатные знаки (они все занимают один байт) по месту на знак табуляции и далее Replace табуляции на пустую строку. 

[sokol92]

Еще один любопытный тест на тему функций работы с текстом.

Код Выделить Развернуть

' Конкатенация всех чисел от 1 до n
Sub TestConcat
 Dim n as Long, i as Long, s as String, msg as String, t as Long, arr, j as Long, k as Long
 n=100000
 
 ' Способ 1 - непосредственно
 s=""
 t=getSystemTicks()
 For i=1 To n
   s=s & CStr(i)
 next i
 msg="Способ 1 : " & (getSystemTicks()-t)
 
 ' Способ 2 - Join
 s=""
 t=getSystemTicks()
 Redim arr(1 To n)
 For i=1 To n
   arr(i)=Cstr(i)
 next i
 s=Join(arr, "")
 msg=msg & Chr(10) & "Способ 2 : " & (getSystemTicks()-t)

 ' Способ 3 - замена по месту
 s=Space(500000)
 j=0
 t=getSystemTicks()
 For i=1 To n
   k=Len(Cstr(i))
   Mid(s, j+1, k)=Cstr(i)
   j=j+k
 next i
 s = Left(s, j)
 msg=msg & Chr(10) & "Способ 3 : " & (getSystemTicks()-t)
 
 Msgbox msg
End Sub

Результаты для Calc (Win 10, 7.2.5.2):

Способ 1 : 2096
Способ 2 : 361
Способ 3 : 7189

Результаты для Excel  (Win 10, Office 2016 32-разрядный):

Способ 1 : 10132
Способ 2 : 24
Способ 3 : 23

Теперь результаты при n=200000 (в способе 3 начальный размер переменной 1200000).

Calc:

Способ 1 : 42271
Способ 2 : 726
Способ 3 : 152388

Excel:

Способ 1 : 51086
Способ 2 : 63
Способ 3 : 54

Я понимаю результаты для Excel. Резкий рост времени первого способа для Calc для меня загадка (тормозит очистка памяти?).

Предварительный вывод - для таких объемов оптимален способ 2. В Excel при дальнейшем росте количества операций метод 3 становится значительно быстрее метода 2. Причина - реализация метода Join. Он достаточно старый и рассчитан на ограниченные ресурсы компьютера. Требуемая память этому методу динамически добавляется фиксированными объемами вместо способа "удвоения".

[kompilainenn]

CLEAN лечится

А вот тут пилят как раз CLEAN если я правильно понимаю https://gerrit.libreoffice.org/c/core/+/129222

[mikekaganski]

CLEAN почти такой же тормоз, как и SUBSTITUTE.

CLEAN лечится классическим математическим приемом. Меняем непечатные знаки (они все занимают один байт) по месту на знак табуляции и далее Replace табуляции на пустую строку.  

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

[mikekaganski]

OK. Сделаю, но не сразу, заодно измерим температуру еще одной кузине (REPLACE).

А какова цель измерения температуры других функций перед написанием бага о SUBSTITUTE? Я бы уже исправил, если бы был баг. А писать несколько проблем сразу в один баг всё равно нельзя. Так что лишние проверки могут только не дать мне исправить, пока есть время на это.

[mikekaganski]

Резкий рост времени первого способа для Calc для меня загадка (тормозит очистка памяти?)

Все эти проблемы (и с Replace в бейсике, и с SUBSTITUTE, и с CLEAN, и с Вашими тестами 1 и 3 в ответе #19) связаны с одним и тем же: особенностями реализации строк в ЛО. Базовый строковый класс - OUString - спроектирован для управления иммутабельным буфером (это count-referenced-объекты). Поэтому когда делается что-то вроде

Код Выделить Развернуть

OUString s = "abc";
s.replaceAll("b", "de");

внутри выделяется память под новую строку, в которую копируется часть из старой строки, часть новых, в процессе возможны дополнительные реаллокации; и в конце концов полученный буфер заменяет старый буфер в s, а старый уничтожается. При работе в цикле это ужасающе медленно, с квадратичной зависимостью.

Join делает это в один проход над массивом, выделяя память в нормальном режиме удвоения буфера.

Написал предложение по изменениям в Basic для решения этой архитектурной особенности.

[sokol92]

Проверил функции Calc на версии 7.2.5.2.

Код Выделить Развернуть

Sub TestReplace
  Dim s as String, i as Long, n as Long, t as Long, msg as String
  n=20000

  With ThisComponent.Sheets(0)
    .getCellByPosition(0,0).setFormula "=REPT("" *""; " & n & ")"
    t=GetSystemTicks()
    .getCellByPosition(0,1).setFormula "=SUBSTITUTE(A1;"" "";""  "")"
    msg="SUBSTITUTE " & (GetSystemTicks()-t)
   
    t=GetSystemTicks
    s=.getCellByPosition(0,0).getString
    s=Replace(s, " ", "*")
    msg=msg & Chr(10) & "Basic Replace " & (GetSystemTicks()-t)
   
    t=GetSystemTicks()
    .getCellByPosition(0,2).setFormula "=TRIM(A1)"
    msg=msg & Chr(10) & "TRIM " & (GetSystemTicks()-t)   
   
    t=GetSystemTicks()
    .getCellByPosition(0,3).setFormula "=CLEAN(REPT(CHAR(9);" & n & "))"
    msg=msg & Chr(10) & "CLEAN " & (GetSystemTicks()-t)   
   
    Msgbox msg
  End With 
End Sub


Результаты при n=20000, 40000, 80000 приведены ниже. Замедление времени пропорционально n*n для SUBSTITUTE и CLEAN, a также Basic Replace заметно. Любопытно, что SUBSTITUTE во много раз быстрее, чем (неисправленная еще в моей версии) Basic Replace.

Код Выделить Развернуть


n             20000     40000     80000
SUBSTITUTE      110       520      2183
Basic Replace  5195     21643     87764
TRIM              2         3         4
CLEAN            10        38       138


Баг про квадратичный рост скорости SUBSTITUTE сейчас напишу.

[mikekaganski]

Любопытно, что SUBSTITUTE во много раз быстрее, чем (неисправленная еще в моей версии) Basic Replace.

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

Регрессия, которую Вы заметили, стала использовать XTextSearch::SearchForward для корректности регистронезависимого поиска. И эта функция внутри производит транслитерацию, при которой происходит куча сложных вещей, несколько аллокаций, обращения к локали, таблицам Unicode и т.п. И это сделало обработку намного тяжелее (Вы это и видели: Ваш оригинальный баг говорит о семи секундах, а регрессия ухудшила его до минуты).

Баг про квадратичный рост скорости SUBSTITUTE сейчас напишу.

Спасибо.

[sokol92]

tdf#147109

Скорость реакции Михаила 4 мин. 25 сек. Скоро догоним рекордсменов по кубику Рубика.

[kompilainenn]

Миша, а все эти фиксы может в 7.3 бэкпортировать?

[sokol92]

Голосую за это!! Для Basic Replace уже сделано, огромное спасибо от миллионов пользователей.