Ну например Томаш Гриштар — автор FASM-а или Джеф Маррисон — автор RWASA. l_inc — Лучший знаток макросов FASM-а, он наверное знает их лучше чем автор FASM.
Если расчитывать адреса вручную — так можно вообще дико оптимизированный код писать. Прям каждый такт выжать. А то сейчас привыкли ленивые программисты медленный код писать, ассемблер всё за них делает…
Я понимаю иронию, но она должна опираться на правильных фактов. Нет такие оптимизации, которые нельзя написать в ассемблере. И это отличает ассемблер от ЯВУ.
Ну или дайте пример.
А да и кроссплатформенность это не священная корова. По крайней мере не для всех.
Кроме того, почему я дал тот пример? — потому что хотел показать, что на ассемблере и на ЯВУ программисты думают по разному. Потому что то что пишется просто на ЯВУ, на ассемблере пишется сложно, а то что на ЯВУ написать сложно, наоборот, на ассемблере пишется просто.
Поэтому я считаю, что учится программировать на ассемблере, читая выход компилятора на ЯВУ нельзя.
С учетом этого становится очевидно что использование хэша выгодно когда КАЖДАЯ строка используется в сравнении несколько раз (или в нескольких сравнениях) Если надо один раз сравнить строку по множеству — смысла считать хэш нет.
Мне все-таки кажется, что вы не понимаете как работает хеш-таблица. Мне кажется, что вы думаете что там в массиве кроме строки сохраняется и хеш этой строки и когда нужно сравнить строку по множеству мы циклим по массиву, только сравниваем не строка с строкой, а хеш с хешем.
Поиск строки в хеш таблицу состоится от:
Вычисление хеша строки которую будем сравнивать — пусть будет h
Смотрим в hash_table[h] — если там 0 то строки нет в массиве. Если там указатель <>0 — то строка есть в массиве.
Это все, даже если в таблице есть миллиардов строк. Поиск будет занимать только одну проверку в массиве. Сложность О(1).
Я сознательно опустил проверки на коллизии, но они не уменьшают скорость, потому что случаются нечасто. Разрешение коллизии просто немножко удлиняет код. Этот код в большинстве случаев не выполняется.
Колизии происходят очень нечасто и поэтому не влияют на производительности алгоритма. А если случаются часто, то надо исправлять баги.
Даже не буду комментировать насчет 5 минут. Вы ещо операционку состряпаете за 5 минут на JS. :P
Но часто выясняется более веселое. Нужно сравнивать строки не как попало, а по умному.
Конечно, когда пишется программа, применяются разные алгоритмы.
Но не понятно, почему этот очевидный факт должен доказывать чего нибудь насчет вполне конкретного примера??? Или сравнивая побайтно легче сделать сравнение UTF-8 с combining characters (например (U+0061)+(U+0301) == (U+00E1))? Не думаю.
Сравнение по хэшу имеет смысл когда много сравнений в неизменяемом множестве строк,
А почему в "неизменяемом"? Вполне может быть и изменяемом.
Потому что в общем случае сравнивать побуквенно эффективнее чем считать и сравнивать хэши.
Нет не так. Побуквенное сравнение будет эффективнее только в некоторых частных случаях. Например когда массив очень небольшой. Но когда массив небольшой и почти сортивован, даже сортировка пузырком может быть быстрее quick сорта.
Но дело в том, что каждой небольшой массив всегда вырастает после две версии программы. ;)
Кстати, мне кажется, что вы не совсем понимаете как работает хеш-таблица. Там нет поиска в массиве и нет циклов, кроме однократного вычисления хеша.
Ну вот один простой пример. Жаль что нет подсветки синтаксиса. Здесь даю только процедуры которые делают работу.
Весь тестовой проект можно скачать здесь. Компилируется в Fresh IDE для Windows, Linux или KolibriOS.
uglobal
hash_table rd 65536
endg
; returns 16 bit hash in EAX!
proc HashFNV1b, .pString
begin
push esi
mov esi, [.pString]
mov eax, $811C9DC5
.hashloop:
cmp byte [esi], 0
je .exit
xor al, byte [esi]
inc esi
imul eax, $01000193
jmp .hashloop
.exit:
; folding to 16 bit.
mov esi, eax
shr esi, 16
xor eax, esi
movzx eax, ax
pop esi
return
endp
; Returns:
;
; CF=0 - the string has been added to the list.
; CF=1 - the string is already in the list or the list is full.
proc AddUniqueToList, .pString
begin
pushad
stdcall HashFNV1b, [.pString]
mov edx, eax ; in order
.put_loop:
mov esi, [.pString]
mov edi, [hash_table+4*eax]
test edi, edi
jnz .compare
; Empty slot has been found
mov [hash_table+4*eax], esi
clc
popad
return
; Collision?
.compare:
cmpsb
jne .yes_collision
cmp byte [esi-1], 0
jne .compare
; the string is already in the list.
stc
popad
return
.yes_collision: ; closed hashing
inc ax
cmp eax, edx
jne .put_loop
; the table is full.
stc
popad
return
endp
Так сравнивать строки обычно нельзя. Потому что длина неизвестна.
А приведите код для поиска через хеш-таблицу? Как-то не очень верится, что он намного проще "=" или "rep cmpsb"
Напишу. Только проще <> короче. Код там будет несколько больше, но его будет проще писать и читать. И конечно будет намного быстрее.
И на ЯВУ тоже можно хеш посчитать, если ставить цель именно оптимизировать выполнение.
Конечно можно. Но там это будет "оптимизация" — то что делается когда иначе никак нельзя. А на ассемблере, это будет проще написать, не думая о производительности.
Я не говорю о компиляторах — они делают свою работу прекрасно.
Я говорю о логике ЯВУ. Давайте дам пример. Пусть требуется сделать поиск строки в массиве строк. На каждом ЯВУ, это проще всего сделать через цикл, ну или (если массив сортирован) через бинарный поиск. Потому что в ЯВУ есть сравнение строк. Там можно написать:
if MyString = Arr[i] then return i
Конечно это будет не так быстро, но коротко, ясно и естественно. А все знают что “Premature optimization is the root of all evil”. Поэтому так и оставят.
А вот, на ассемблере, этот подход уже не так удобен. Потому что там сравнение строк нет. Придется сравнивать побайтно. Появятся вложенные циклы. Не хватит регистров. Читаемость кода ухудшится.
Программист, который раньше писал на ЯВУ так и напишет. Потому что по другому он не мыслит. Он знает что это самое простое решение, а то что получается плохо, это из за дурацкого ассемблера.
А на ассемблере, намного проще сделать поиск через хеш таблицу. Потому что там все циклы одиночные, короткие и ясные. Код получится намного проще и понятнее. Даже совершенно наивная реализация хеш функции сделает поиск намного быстрее. И заметьте — никакие ранние оптимизации — пишем так как проще, а не думаем о скорости. Она получается сама.
Этот пример не высосан из пальца. Именно так получилось однажды, когда организовали битвы "assembly vs c++" на одном болгарском форуме. Надо было сделать парсер markdown (кстати, парсер в AsmBB результат именно этой битвы). Так первая версия на ассемблере была в 80 раз быстрее чем на C++, только из за этого.
Дело не в то как компилятор компилирует, а в то что компилирует он код, который написан на ЯВУ. Вся логика у этого кода не ассемблерная, а именно логика ЯВУ. Человек, который писал этот код, скорее всего написал эго так как легче и лучше именно C или на Паскаль.
Когда человек пишет на ассемблер, он пишет так как легче и лучше писать именно на ассемблере.
Как проще всего зайти в ассембер на уровне «оптимизация некоторых функций» программисту, который кроме программирования на си микроконтроллера, работал только с высокоуровневыми языками?
"Зайти" на уровне "оптимизация" не получится. Оптимизация, это высший пилотаж. Поэтому лучше просто начать писать на ассемблере неоптимальный код. Скачайте FASM или Fresh IDE, почитайте примеры которые в архиве. Напишите небольшие программы, которые вам нужны.
Общайтесь на форуме FASM. Спрашивайте на stackoverflow. Постепенно все образуется.
Не стоит делать то, что многие рекомендуют — читать выход компилятора на C. Люди пишут на ассемблере совершенно по другому.
Смысл был в том, чтобы показать скорость разработки аналогичного проекта на языке высокого уровня. Я не ставил себе цель сравнивать миллисекунды.
Я тоже провел эксперимент. Мне очень трудно считать сколько времени отнимет та или другая задача. Поэтому, решил реализовать кеширование HTTP (как советовали), но измерить точное время работы.
Эта задача очень подходит под эксперимент, потому что код которого надо было менять писался весной и больше никогда не менялся (ну может быть были некоторые багфиксы). Так что задача получается очень реалистична. Надо менять код, которой писался давным давно, надо сориентироваться и потом поменять его.
Получилось ровно 78 минут.
Можно было и быстрее, но мне не хотелось удалять старую БД, поэтому пришлось писать и код который рендировал все старые посты на сервере.
Но зачем, кроме фана, нужен ассемблер в задаче, где нет никаких вычислений, я все же не понимаю.
А разве фан, это плохо?
Я пишу на ассемблере много чего. Часть моего кода (например программы управления промышленного оборудования) закрытая. Можно посмотреть некоторые картинки здесь.
A вообще, больше всего нравится писать десктоп приложения. Но написание AsmBB было мне очень полезно. Я научил что это FastCGI, SMTP, XSS и много всего из мира WWW/HTTP. Разве это плохо?
Ваши все вычисления предполагают, что разработчики будут работать в одинаковом темпе, во все время жизни проекта. Работает сервер, тысячи посетители посещают сайт, читают, пишут, общаются, а в то же время 5 девелоперы, каждый день, 8 часов подряд, пишут новый код, фиксят баги и т.д. И так в продолжении 10..20 лет.
Но ведь так не бывает. Разработка всегда движется по экспоненте — в начале все работают много, потом работа уменьшается и приоритеты смещаются — примерно исправляются ошибки.
Во вторых, вы пишете насчет разработки очень специализированного софта, который будет работать на одном сервере и нигде больше. Но так тоже далеко не всегда. Если взять например SMF — там тоже разработчики работают все время (и опять интенсивность работ совсем не всегда одинакова), но их программа установлена на десятки тысячи серверов и суммарные расходы на хостинг просто сумасшедшие.
Ну например Томаш Гриштар — автор FASM-а или Джеф Маррисон — автор RWASA. l_inc — Лучший знаток макросов FASM-а, он наверное знает их лучше чем автор FASM.
Я понимаю иронию, но она должна опираться на правильных фактов. Нет такие оптимизации, которые нельзя написать в ассемблере. И это отличает ассемблер от ЯВУ.
Ну или дайте пример.
А да и кроссплатформенность это не священная корова. По крайней мере не для всех.
Кроме того, почему я дал тот пример? — потому что хотел показать, что на ассемблере и на ЯВУ программисты думают по разному. Потому что то что пишется просто на ЯВУ, на ассемблере пишется сложно, а то что на ЯВУ написать сложно, наоборот, на ассемблере пишется просто.
Поэтому я считаю, что учится программировать на ассемблере, читая выход компилятора на ЯВУ нельзя.
Это не подмена, потому что это одна и та же задача. Код будет тот же самый только будет на инструкции меньше:
Мне все-таки кажется, что вы не понимаете как работает хеш-таблица. Мне кажется, что вы думаете что там в массиве кроме строки сохраняется и хеш этой строки и когда нужно сравнить строку по множеству мы циклим по массиву, только сравниваем не строка с строкой, а хеш с хешем.
Поиск строки в хеш таблицу состоится от:
Это все, даже если в таблице есть миллиардов строк. Поиск будет занимать только одну проверку в массиве. Сложность О(1).
Я сознательно опустил проверки на коллизии, но они не уменьшают скорость, потому что случаются нечасто. Разрешение коллизии просто немножко удлиняет код. Этот код в большинстве случаев не выполняется.
Колизии происходят очень нечасто и поэтому не влияют на производительности алгоритма. А если случаются часто, то надо исправлять баги.
Даже не буду комментировать насчет 5 минут. Вы ещо операционку состряпаете за 5 минут на JS. :P
Конечно, когда пишется программа, применяются разные алгоритмы.
Но не понятно, почему этот очевидный факт должен доказывать чего нибудь насчет вполне конкретного примера??? Или сравнивая побайтно легче сделать сравнение UTF-8 с combining characters (например (U+0061)+(U+0301) == (U+00E1))? Не думаю.
А почему в "неизменяемом"? Вполне может быть и изменяемом.
Нет не так. Побуквенное сравнение будет эффективнее только в некоторых частных случаях. Например когда массив очень небольшой. Но когда массив небольшой и почти сортивован, даже сортировка пузырком может быть быстрее quick сорта.
Но дело в том, что каждой небольшой массив всегда вырастает после две версии программы. ;)
Кстати, мне кажется, что вы не совсем понимаете как работает хеш-таблица. Там нет поиска в массиве и нет циклов, кроме однократного вычисления хеша.
Хеш вычисляется только однажды, а сравнение делается с каждой строке в массиве. Посмотрите ниже — я дал пример.
Ну вот один простой пример. Жаль что нет подсветки синтаксиса. Здесь даю только процедуры которые делают работу.
Весь тестовой проект можно скачать здесь. Компилируется в Fresh IDE для Windows, Linux или KolibriOS.
uglobal hash_table rd 65536 endg ; returns 16 bit hash in EAX! proc HashFNV1b, .pString begin push esi mov esi, [.pString] mov eax, $811C9DC5 .hashloop: cmp byte [esi], 0 je .exit xor al, byte [esi] inc esi imul eax, $01000193 jmp .hashloop .exit: ; folding to 16 bit. mov esi, eax shr esi, 16 xor eax, esi movzx eax, ax pop esi return endp ; Returns: ; ; CF=0 - the string has been added to the list. ; CF=1 - the string is already in the list or the list is full. proc AddUniqueToList, .pString begin pushad stdcall HashFNV1b, [.pString] mov edx, eax ; in order .put_loop: mov esi, [.pString] mov edi, [hash_table+4*eax] test edi, edi jnz .compare ; Empty slot has been found mov [hash_table+4*eax], esi clc popad return ; Collision? .compare: cmpsb jne .yes_collision cmp byte [esi-1], 0 jne .compare ; the string is already in the list. stc popad return .yes_collision: ; closed hashing inc ax cmp eax, edx jne .put_loop ; the table is full. stc popad return endpТак сравнивать строки обычно нельзя. Потому что длина неизвестна.
Напишу. Только проще <> короче. Код там будет несколько больше, но его будет проще писать и читать. И конечно будет намного быстрее.
Конечно можно. Но там это будет "оптимизация" — то что делается когда иначе никак нельзя. А на ассемблере, это будет проще написать, не думая о производительности.
Я не говорю о компиляторах — они делают свою работу прекрасно.
Я говорю о логике ЯВУ. Давайте дам пример. Пусть требуется сделать поиск строки в массиве строк. На каждом ЯВУ, это проще всего сделать через цикл, ну или (если массив сортирован) через бинарный поиск. Потому что в ЯВУ есть сравнение строк. Там можно написать:
Конечно это будет не так быстро, но коротко, ясно и естественно. А все знают что “Premature optimization is the root of all evil”. Поэтому так и оставят.
А вот, на ассемблере, этот подход уже не так удобен. Потому что там сравнение строк нет. Придется сравнивать побайтно. Появятся вложенные циклы. Не хватит регистров. Читаемость кода ухудшится.
Программист, который раньше писал на ЯВУ так и напишет. Потому что по другому он не мыслит. Он знает что это самое простое решение, а то что получается плохо, это из за дурацкого ассемблера.
А на ассемблере, намного проще сделать поиск через хеш таблицу. Потому что там все циклы одиночные, короткие и ясные. Код получится намного проще и понятнее. Даже совершенно наивная реализация хеш функции сделает поиск намного быстрее. И заметьте — никакие ранние оптимизации — пишем так как проще, а не думаем о скорости. Она получается сама.
Этот пример не высосан из пальца. Именно так получилось однажды, когда организовали битвы "assembly vs c++" на одном болгарском форуме. Надо было сделать парсер markdown (кстати, парсер в AsmBB результат именно этой битвы). Так первая версия на ассемблере была в 80 раз быстрее чем на C++, только из за этого.
Дело не в то как компилятор компилирует, а в то что компилирует он код, который написан на ЯВУ. Вся логика у этого кода не ассемблерная, а именно логика ЯВУ. Человек, который писал этот код, скорее всего написал эго так как легче и лучше именно C или на Паскаль.
Когда человек пишет на ассемблер, он пишет так как легче и лучше писать именно на ассемблере.
"Зайти" на уровне "оптимизация" не получится. Оптимизация, это высший пилотаж. Поэтому лучше просто начать писать на ассемблере неоптимальный код. Скачайте FASM или Fresh IDE, почитайте примеры которые в архиве. Напишите небольшие программы, которые вам нужны.
Общайтесь на форуме FASM. Спрашивайте на stackoverflow. Постепенно все образуется.
Не стоит делать то, что многие рекомендуют — читать выход компилятора на C. Люди пишут на ассемблере совершенно по другому.
А, да. Весь код, который менялся за те 78 минут здесь: HTTPCache
Я тоже провел эксперимент. Мне очень трудно считать сколько времени отнимет та или другая задача. Поэтому, решил реализовать кеширование HTTP (как советовали), но измерить точное время работы.
Эта задача очень подходит под эксперимент, потому что код которого надо было менять писался весной и больше никогда не менялся (ну может быть были некоторые багфиксы). Так что задача получается очень реалистична. Надо менять код, которой писался давным давно, надо сориентироваться и потом поменять его.
Получилось ровно 78 минут.
Можно было и быстрее, но мне не хотелось удалять старую БД, поэтому пришлось писать и код который рендировал все старые посты на сервере.
А разве фан, это плохо?
Я пишу на ассемблере много чего. Часть моего кода (например программы управления промышленного оборудования) закрытая. Можно посмотреть некоторые картинки здесь.
A вообще, больше всего нравится писать десктоп приложения. Но написание AsmBB было мне очень полезно. Я научил что это FastCGI, SMTP, XSS и много всего из мира WWW/HTTP. Разве это плохо?
А скорость разработки пока так:
3 дня и 27 коммитов, а версия, согласитесь что сырая. (Кстати, вы начали писать 3-его Января?!)
У меня, для v1.0 понадобилось 54 коммитов.
Так что если привести эту работу к v1.0 по моему брой коммитов будет очень близко к те 54.
О! Уважаю! Теперь давайте приводить в вид, которого можно было сравнивать:
Насчет оценки быстродействия может и хватит — но, конечно если добавите измеритель (см. 1)
Но насчет сравнения времени разработки не хватит, потому что у вас нет:
А чтобы сделать все это нужно время. И так эти 12 часов превратятся в намного больше.
0.97с это долго? А сравниваете с чем?
Все это так, но не совсем.
Ваши все вычисления предполагают, что разработчики будут работать в одинаковом темпе, во все время жизни проекта. Работает сервер, тысячи посетители посещают сайт, читают, пишут, общаются, а в то же время 5 девелоперы, каждый день, 8 часов подряд, пишут новый код, фиксят баги и т.д. И так в продолжении 10..20 лет.
Но ведь так не бывает. Разработка всегда движется по экспоненте — в начале все работают много, потом работа уменьшается и приоритеты смещаются — примерно исправляются ошибки.
Во вторых, вы пишете насчет разработки очень специализированного софта, который будет работать на одном сервере и нигде больше. Но так тоже далеко не всегда. Если взять например SMF — там тоже разработчики работают все время (и опять интенсивность работ совсем не всегда одинакова), но их программа установлена на десятки тысячи серверов и суммарные расходы на хостинг просто сумасшедшие.