A64m
это не перевернуто это же list string вот в эмелях перевернуто там string list
Кабачок
отдельный токен, насколько я знаю
A64m
@aragaer да у всех жрет цпу, просто дев.нул быстро байты принимает, видно предполагается что читательбудет подтормаживать
A64m
тогда конечно писатель уже 100% не отъест
Aragaer
да я и в файл когда пишу, то же самое
Ilya
Alexander
@aragaer уже когда в |md5 пишешь не так
Aragaer
я еще раз повторю, callgrind показывает, что треть времени моя сишная реализация занята выполнением memcpy
Alexander
@aragaer выкинь memcpy
Alexander
на коротких строках безтолку
Aragaer
а чем еще слова копировать в выходной буфер?
Alexander
посимвольно
Dmitry
лучше не будет
Alexander
если сильный духом и выровнято но по словам сначала
Dmitry
там компилятор memcpy вроде обрабатывает
Alexander
@voidlizard ну у меня чуть-чуть лучше вышло без memcpy
Alexander
ну как чуть-чуть - статистически значимо
Alexander
поидее memcpy тоже не должен просить ведро копировать, но для начала он должен проверить что строки мелкие и т.п.
Alexander
я бы предложил копировать кусочками по uint64_t, uint32_t, uint8_t
eahqzsr
Сделал. Тут вроде несложно. Задача явно memory-bound. Значит число операций считать не будем, IO тоже считать не будем (уже посчитали с dd)
Парсинг входных данных по времени ничтожен, так как его время линейно зависит от входа, а выход у нас квадратичный.
Что остаётся? Лепка строк.
Для этого мы N^2 раз будем читать suf, и N^2 раз писать (pref + 1 + suf + 1). Итого N^2 * (2suff + pref + 2) оперативной памяти, suff = pref = 5 (в байтах), итого 17N^2 байтов.
Пропускную способность взял 15 гигабайт/с, не знаю сколько сейчас на современных компах на DDR4, но должно быть около того. Для оценки сойдёт.
На длине входа N = 1e4 (что у нас и есть) имеем
17e8 [байт] / 15e8 [байт/c], что примерно равно 1.2 сек.
Ну в общем вывод такой, что вы уже около теоретического значения маячите, что довольно хорошо!
Где-то ошибка. На выход пишется 1 Гбайт. Соответственно столько же читается. Если мы не учитываем latency, но это никак не 1сек.
Alexander
но оно не выровняно, так что толку не будет
Кабачок
__m256
Alexander
да да
Alexander
_m512 и на xeon phi
Alexander
кстати ни у кого нету ненужного поиграться?
A64m
да мемкопи адово быстро работает, он и симды часто использует же, его посимвольным копированием не обогнать
Ilya
Где-то ошибка. На выход пишется 1 Гбайт. Соответственно столько же читается. Если мы не учитываем latency, но это никак не 1сек.
Там ниже я исправил. Ошибся на один порядок. В итоге 0.1
Ilya
Там ниже я исправил. Ошибся на один порядок. В итоге 0.1
Делить надо было не на 15e8, а на 15e9
Anonymous
@qnikst уже можно пинать про бумаги?
Alexander
да, но вчера ж назвали с @A64m_qb0
Anonymous
не видел
Alexander
щас референсы точные найду
Aragaer
но оно не выровняно, так что толку не будет
src для копирования можно выровнять, а вот dst не получится
Aragaer
у меня была дурная мысль как-то состыковывать префикс и суффикс вокруг границы слова, но получившуюся пару все равно надо копировать
Alexander
[1] D. Coutts, “Stream Fusion: Practical shortcut fusion for coinductive sequence types,” 2010. <- диссер коутса
Alexander
хаха а статей Лещинского то у меня и нет
Alexander
https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/haskell-beats-C.pdf
вот начиная с этого сообщения
Alexander
@anarchostatist ^
Anonymous
ок спс
A64m
http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.104.7401
A64m
а, там пдф-то стух
Dmitry
в смысле?
Алексей
A64m
Geoffrey Mainland, Roman Leshchinskiy, Simon Peyton Jones:
Exploiting vector instructions with generalized stream fusion
A64m
https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/haskell-beats-C.pdf
A64m
и по фолдр-билд https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/deforestation-short-cut.pdf
A64m
А что там у коммонлиспа-то, кстати?
Aragaer
я не настоящий лиспер, поэтому все плохо
A64m
насколько плохо?
Aragaer
наивная реализация раз в 40 медленнее С, попытка добавить буферизацию вывода - еще в полтора раза мадленнее
Aragaer
причем он там на 100% грузит проц и какие-то байтики перекидывает по одному
Alexander
@voidlizard а что у тебя за железо, там solhov спрашивает на жуйке
Dmitry
да какой-то ноут, я не помню. еще до хасвела
Кабачок
@aragaer это скомпилированное? какая реализация?
Dmitry
у меня на столе стоит core i7 c хасвелом, но мне лень туда ходить
Aragaer
не, компилировать я еще не умею. sbcl
Aragaer
ща кину в гист
Dmitry
@qnikst короче, core i7 до хасвела.
model name : Intel(R) Core(TM) i7-3517U CPU @ 1.90GHz
Aragaer
https://gist.github.com/aragaer/4a4854028ad12e16c3af5ed371cacc07
Dmitry
@qnikst а что, спец. олимпиада в жуик перекинулась?
Aragaer
блин, как телограмму объяснить, что картинку не брать?
Alexander
@voidlizard да
分解物質
dmz@zen ~/tmp/bsfuck $ time ./v-stream < ./49zGQ6Zt.txt > /dev/null
real 0m1.652s
user 0m1.624s
sys 0m0.024s
https://gist.github.com/yellow-apple/69993c04f8d9afc0d72c56f27e55187f
бенчмаркните
Alexander
я там выругался что си с printf не падает
Alexander
а они стали говорить, что я говно а не программист т.к. debug print решил использовать
分解物質
у меня
$ time ./a.out < ./49zGQ6Zt.txt > /dev/null
real 0m0.009s
user 0m0.007s
sys 0m0.002s
Dmitry
блин, меня теперь не пускают коменты в жуике смотреть без логина
Alexander
ну я попросил их самих написать, похоже заинтересовались
Alexander
там косяк
Alexander
жми на дату
Aragaer
про лисп - 40 с лишним строк, если без буферизации, то только строки 9, 10 и 29-40
Alexander
откроется
Alexander
@voidlizard ^
Alexander
UI дебильный должны пофиксить на этой неделе
Alexander
@yellow_apple а в чем отличие от моей версии кстати, часть очень похоже но судя по времени работает в 10 раз быстрее
Vladislav
Alexander
без учета того что разные компы
分解物質
@yellow_apple а в чем отличие от моей версии кстати, часть очень похоже но судя по времени работает в 10 раз быстрее
незнаю, не разбирался в чужих версиях
Dmitry
@qnikst @yellow_apple md5sum не сходится, в выхлопе какая-то шляпа
Dmitry
@yellow_apple выхлоп на два порядка меньше, чем должен быть