В последнее время у меня большой интерес вызывает язык программирования Go — слишком много плюшек его использование сулит программисту. Хочется back-end для новых игр написать на нем, но существующая и отлаженная кодовая база на Ruby мешает этому.
Поэтому я решил двигаться небольшими итерациями и начал с переписывания микросервисов применяемых в играх на Go.
Во всех микросервисах есть подключение к базам Redis. Обычно используется 8 баз Redis, где игра хранит данные.
Строка с частью запроса к Redis преобразуется с помощью SHA-1 в шестнадцатеричное число. Затем находится остаток от деления этого числа на 8. И в зависимости от него данные записываются/читаются из нужной базы.
Исходный вариант на ruby, который я решил переписать на Go.
def node0(text)
return Integer('0x'+Digest::SHA1.hexdigest(text))%8
end
К сожалению или к счастью такой подход в лоб на Go не сработал. Получаемая 16-ричная строка представляла слишком большое число. В тип int64 это число не помещалось.
Как решить проблему?
У нас 8 баз и 16-ричное число, от которого надо взять остаток от деления на 8.
Ответ.
Первое, что приходит на ум. Нам достаточно знать последний символ 16-ричного числа, чтобы посчитать остаток от деления всего числа на 8.
Мы легко можем переписать решение на ruby с учетом вышесказанного так:
def node1(text)
s = Digest::SHA1.hexdigest(text)
return Integer('0x'+s[s.size-1, 1]) % 8
end
То же самое, но на Go:
func node1 (text string) int64 {
h := sha1.New()
h.Write([]byte(text))
sha1_hash := hex.EncodeToString(h.Sum(nil))
sha1_hash_len := len(sha1_hash)
last := sha1_hash[sha1_hash_len-1:sha1_hash_len]
value, _ := strconv.ParseInt(last, 16, 64) //int64
return value % 8
}
Второе, что удачно оказалось
В процессе написания кода, представленного выше, выяснилось, что Go в ходе выполнения SHA-1 представляет число в виде набора десятичных чисел, а потом уже их приводит к 16-ричному виду. Поскольку нам нужен остаток от деления, то мы можем просто взять последнее десятичное число вместо 16-ричного последнего символа и сэкономить на преобразованиях из одной системы счисления в другую.
func node2 (text string) int64 {
h := sha1.New()
h.Write([]byte(text))
mas := h.Sum(nil) // "hello world" -> [42 174 108 53 201 79 207 180 21 219 233 95 64 139 156 233 30 232 70 237]
return int64(mas[len(mas)-1]) % 8 // Берем последний элемент массива. Это целое десятичное число. И считаем остаток от деления на 8
}
Этот финт позволил еще быстрее вычислять то, что необходимо. Но на Ruby такой трюк выполнить не удалось. Поэтому корректнее сравнивать производительность node1 из Ruby и node1 из Go.
И так какая скорость работы у всего представленного?
Как я решил протестировать:
Посчитать, в какую базу данных положить данные, относящиеся к каждому из миллиона пользователей.
На Ruby:
for i in 1..1000000 do
node1("user:"+i.to_s)
end
и на Go:
for i := 1; i <= 1000000; i++ {
node1("user:"+string(i))
}
Полный код можно посмотреть на github.
Для чистоты эксперимента я запускал каждый скрипт по 10 раз, и ниже представлены средние значения.
Код запускался на версиях Ruby 1.8.7 и 2.1.3. Версия Go была 1.4.2
Значения в секундах. Меньше — лучше.
Ruby 1.8.7
node0 — 22.32
node1 — 17.24
node11 — 16.81
Ruby 2.1.3
node0 — 15.46
node1 — 11.15
node11 — 11.05
Go 1.4.2
node1 — 6.15
node2 — 4.36
Почему такие старые версии Ruby?
Код многих проектов я начал создавать 4-5 лет назад. По мере возможности я переносил его на новые версии Ruby. В частности на 2.1.3. Согласен, что на последней версии Ruby 2.2.2 результаты могут быть лучше, но явно не в два раза.
Выводы
- 1. Go 1.4.2 быстрее старых версий Ruby в 3 раза. И быстрее современных версий в 2 раза.
- 2. Ruby неплохо оптимизировали с версии 1.8.7 до 2.1.3. Прирост скорости на 25-30%.
- 3. Ruby, ты был верным другом и соратником, мы многое прошли вместе, но… я встретил Go. Теперь мне с ним по пути.
Комментарии (37)
maximw
10.06.2015 21:26+2Если уж вы оптимизируете такие вещи, то, имхо, лучше взять md5, вместо sha1, он вроде как быстрее считается. А еще лучше что-нить менее криптографическое, но с равномерным распределением, типа crc32, и не будет проблем с размером int.
AlexeiZhuravlev Автор
10.06.2015 21:28-3Согласен с вами, но исторически сложилось, что используется именно sha1. Поэтому и на Go приходится с ним работать.
jj_killer
10.06.2015 23:18В случае с Ruby используется OpenSSL (если библиотека установлена), а это значит, что при подсчете SHA1 и MD5 используются нативные инструкции процессора (если он поддерживает AES instruction set и версия OpenSSL > 1.0.1) и особой разницы нету. В данном случае, большая часть времени расходуется на аллокацию объектов в MRI.
С другой стороны, реализация SHA1 в Go написана на самом Go (даже без Go asm). Так что трудно сказать без профилирования насколько Go реально быстрее в этом случае.
neolink
10.06.2015 23:32про реализацию на Go — github.com/golang/go/tree/master/src/crypto/sha1, файлики *.s это ассемблеры
в Go в этом тесте тоже процентов 30 времени как раз на аллокацию и конкатенацию строк тратитсяjj_killer
10.06.2015 23:45О файлики эти пропустил, да. В любом случае, в ассемблерных файлах нету упоминания Intel SHA Extensions (выше я почему-то посчитал, что поддержка SHA быть в AES Instruction Set, но она реализована как часть SSE), а значит все равно некоректно сравнивать эти реализации только по общему времени исполнения. Надо смотреть на реальное время выполнения каждой функции/метода.
robert_ayrapetyan
10.06.2015 21:30+2Боретесь за миллисекунды и используете SHA1?
Попробуйте code.google.com/p/xxhash, в руби точно есть оббертка.
п.с. сверху опередилиAlexeiZhuravlev Автор
10.06.2015 21:31Спасибо за интересную ссылку. В свободное время надо будет попробовать.
printercu
10.06.2015 21:43+3> Но на Ruby такой трюк выполнить не удалось.
Возможно все
text = 'asd' Digest::SHA1.digest(text)[-1].ord & 0x7 == Integer('0x'+Digest::SHA1.hexdigest(text))%8 # true
aktuba
10.06.2015 22:38А время точно в секундах? Как-то слабо верится, что php быстрее go: 3v4l.org/bA6a5
AlexeiZhuravlev Автор
10.06.2015 22:48Точно. Возможно, что в вашем случае какой-то быстрый процессор используется. Я у себя тестировал на обычном ноутбуке.
И обратите внимание сколько памяти потребляется в вашем случае. В среднем 20 MiB и для hhvm почти 80! У меня Go 1,5, а Ruby 2,6 МБ использовали.
PQR
10.06.2015 23:08-4То, что PHP иногда быстрее Go, уже были примеры: github.com/dimroc/etl-language-comparison/pull/12
neolink
10.06.2015 23:13чтобы говорить, что код быстрее нужно сравнивать одинаковые вещи,
об первой вещи собственно по вашей ссылке и написано go работает с unicode
а вторая, что время для go включает ещё и компиляцию: github.com/dimroc/etl-language-comparison/blob/master/run_go
sayber
10.06.2015 23:10Код Go с github
[ `go run test.go` | done: 1.933083629s ] node1: 957075514 node2: 743407604
neolink
10.06.2015 23:42про Go
~30% времени тратится на аллокации строк в цикле
также используйте sha1.Sum([]byte(text)) это будет быстрее:
mas := sha1.Sum([]byte(text))
return int64(mas[len(mas)-1]) % 8
также если вы не используете в коде горутины то GOMAXPROCS на вашем коде никак не скажется
ну и тесты производительности в Go принято делать через bench (http://dave.cheney.net/2013/06/30/how-to-write-benchmarks-in-go)neolink
10.06.2015 23:49оригинальный код:
node1: 1118402612
node2: 772230494
использование sha1.Sum (без пре аллокации)
node1: 837969082
node2: 485179839
пре-аллоцированные данные
node1: 738665390
node2: 478114103
пре-аллокация и sha1.Sum:
node1: 545527947
node2: 286142563
zencd
11.06.2015 10:24+5Стоит ли вобще начинать сравнивать две платформы если оригинальный код настолько глуп (я только про код). Хэшировать строку в big integer, конвертировать в hex string, конкатенировать с «0x», парсить обратно в число О_о Чудовищный подход.
crc32, у которого более подходящий интерфейс для этого (возвращает число), работает в 5.5 раза — о, чудо — быстрее:
Скрытый текстrequire 'digest' require 'zlib' max = 2000000 def measure(title) start = Time.now yield if block_given? elapse = Time.now - start puts "#{title}: #{elapse} sec" end measure("with_crc32") { (0..max).each do |i| Zlib.crc32("text #{i}") % 8 end } measure("with_sha1") { (0..max).each do |i| Integer('0x'+Digest::SHA1.hexdigest("text #{i}"))%8 end }
youlose
11.06.2015 11:43Можете не переходить на Go, я ваш пример на руби почти в 2 раза ускорил:
require 'benchmark/ips'
require 'digest'
text = 'Preved, medved!!!'
Benchmark.ips do |x|
x.report('habr:') { Integer('0x'+Digest::SHA1.hexdigest(text))%8 }
x.report('my_optimization:') { Digest::SHA1.digest(text)[-1].ord & 7 }
end
===
ruby 1.rb
Calculating — habr: 26.803k i/100ms
my_optimization: 41.454k i/100ms
— habr: 359.737k (± 0.9%) i/s — 1.823M
my_optimization: 646.808k (± 1.1%) i/s — 3.233M
1. Преобразовывать весь хэш в число нет смысла, если вам всего-то надо остаток от деления на 8 узнать
2. Самый быстрый способ узнать остаток от деления — логическое AND с 3 последними битамиAlexeiZhuravlev Автор
11.06.2015 12:03Вчера пользователь printercu в комментарии выше как раз и предложил такой вариант ускорения. Он получается почти в 2 раза быстрее чем оригинальный код.
youlose
11.06.2015 12:12Ааа, ну я кода не увидел и бенчмаркопопугаев, потому, наверное, просмотрел его вариант (надо было хобя бы сослаться на него в самой статье.
P.S. да, про crc32 он верно предложил.
youlose
11.06.2015 12:05+1Ещё добавлю:
учитывая что на моём компе редис работает со скоростью 73855.24 requests per second
вы уверены что вам надо оптимизировать именно функцию хеширования?AlexeiZhuravlev Автор
11.06.2015 12:12У меня на серверах есть несколько скриптов на руби, которые с определенной периодичностью обращаются к редису и что-то делают. Например, считают рейтинги игроков, выдают бонусы, чистят старые данные из редиса и т.д.
И я решил переписать часть этих скриптов на Go (чтобы более детально познакомится с языком с прицелом для будущих проектов). В процессе переписывания мне и стало интересно — на сколько Go быстрее Ruby в этой задаче.
Поэтому у меня особой задачи по оптимизации функции хеширования и не было (и так все достаточно быстро работает). Только спортивный интерес, который и перерос в этот топик.youlose
11.06.2015 12:17Кстати, запустил ваш код на Go у себя на компе, получилось ~1 млн/сек хешей на node2 функции. Для языка с строгой типизацией думал круче будет (видимо там ещё что-то можно улучшить).
AlexeiZhuravlev Автор
11.06.2015 12:23Благодаря комментариям, это вариант самый быстрый на go:
func node3 (text string) int64 { mas := sha1.Sum([]byte(text)) return int64(mas[len(mas)-1]) % 8 }youlose
11.06.2015 13:28Пришлось посмотреть как бенчмаркать в Go… не так круто как у Ruby…
~2_347_417 / s на моём компе
Уже нормально.
prijutme4ty
12.06.2015 13:47Эм. Даже без всякой магии с битовыми масками, вы 25% скорости тратите тупо на конкатенацию строк.
require 'digest' require 'benchmark' text = 'Hello world' N=1_000_000 Benchmark.bm do |x| x.report{ N.times{ Integer('0x'+Digest::SHA1.hexdigest(text)) } } x.report{ N.times{ Digest::SHA1.hexdigest(text).to_i(16) } } end
user system total real
3.360000 0.000000 3.360000 ( 3.373353)
2.600000 0.000000 2.600000 ( 2.593256)AlexeiZhuravlev Автор
12.06.2015 19:47-1Спасибо, кэп. Вы все прояснили!
prijutme4ty
12.06.2015 19:54+2Если вам было так очевидно, что не надо конкатенировать строку, чтобы перевести ее в HEX, а пользоваться стандартными методами, то зачем вы это делали?
Zelgadis
16.06.2015 02:34Ну а серьезно что вы этим бенчмарком показали? Кроме того, что вы плохой ruby разработчик?
Все нормальные разработчики на руби знают, что создавать строку на руби длинее 23 символов лишний раз не надо.AlexeiZhuravlev Автор
16.06.2015 08:44Нормальный разработчик на руби, Вы где больше 23 символов насчитали?
IncorrecTSW
Ответ на вопрос в заголовке вроде бы и так очевиден.
К слову benchmarksgame.alioth.debian.org/u64q/compare.php?lang=go&lang2=yarv
AlexeiZhuravlev Автор
Спасибо за ссылку. Моя статья не претендует на такой объем исследования и сравнения. Только лишь небольшая частичка.
icoz
Ну, может, тогда не надо такие громкие заголовки писать? Содержание статьи не соответствует названию. Отсюда и минусы… (на момент написания комментария голосовалка статьи показывает -2)