A🌚
Size: a a a
2020 December 11
БС
Как ты далеко залез. Тут проседание будет только при итерации вроде как
да при любом доступе.. Даже просто при добавлении.. Ведь питоновский список увеличивается не при каждой вставке, поэтому в среднем O(1), но без дополнительной косвенной адресации..
Но всё что я пишу, в питоне пофиг...
Но всё что я пишу, в питоне пофиг...
SA
А вообще интересно, хотя заниматься такого рода оптимизациями в питоне мне кажется странным
Конкретно в прикладном коде - очень может быть. Однако прикладной код неявно полагается на то, что базовые блоки достаточно оптимизированные
БС
поэтому сейчас dict в питоне это массив и там упорядочивание следствие оптимизаций получилось.
KK
объясняется это тем, что оптимально делать структуры в размер кэш линии (16 байт (или dwordов) 10 лет назад было, как сейчас -- хз), чтобы было как можно меньше вытеснений из кеша и конкуренции..
На днях бенчмаркал одну простую функцию на Rust (перетащил её из С-шного кода Pillow).
Задача простая - на вход поступает int, в котором фактически лежит дробное число в fixed-point представлении и нужно получить целую часть этого "дробного" в виде байта (отрицательные числа вернуть как 0, а всё что больше 255 вернуть как 255). C-функция делала битовое смещение в право, прибавляла константу и результат использовала как индекс в глобальном константном массиве, что бы получить на выход байт.
Я сначала конечно не поверил что такое простое дело будет работать быстрее чем if ... elif ... else но оказалось что всё таки немного быстрее работало. Видимо прочитать из кеша один байт быстрее чем пройтись по паре условных jmp-ов.
Задача простая - на вход поступает int, в котором фактически лежит дробное число в fixed-point представлении и нужно получить целую часть этого "дробного" в виде байта (отрицательные числа вернуть как 0, а всё что больше 255 вернуть как 255). C-функция делала битовое смещение в право, прибавляла константу и результат использовала как индекс в глобальном константном массиве, что бы получить на выход байт.
Я сначала конечно не поверил что такое простое дело будет работать быстрее чем if ... elif ... else но оказалось что всё таки немного быстрее работало. Видимо прочитать из кеша один байт быстрее чем пройтись по паре условных jmp-ов.
RB
поэтому сейчас dict в питоне это массив и там упорядочивание следствие оптимизаций получилось.
а какие еще варианты есть? я только с разреженным массивом помню
ну это я в гугле посмотрю, просто мысля вслух получилась
ну это я в гугле посмотрю, просто мысля вслух получилась
SA
linear probing и buckets - вот 2 основных подхода
VR
а кому-то удалось на mac big sur поставить pip_pypy3?
БС
На днях бенчмаркал одну простую функцию на Rust (перетащил её из С-шного кода Pillow).
Задача простая - на вход поступает int, в котором фактически лежит дробное число в fixed-point представлении и нужно получить целую часть этого "дробного" в виде байта (отрицательные числа вернуть как 0, а всё что больше 255 вернуть как 255). C-функция делала битовое смещение в право, прибавляла константу и результат использовала как индекс в глобальном константном массиве, что бы получить на выход байт.
Я сначала конечно не поверил что такое простое дело будет работать быстрее чем if ... elif ... else но оказалось что всё таки немного быстрее работало. Видимо прочитать из кеша один байт быстрее чем пройтись по паре условных jmp-ов.
Задача простая - на вход поступает int, в котором фактически лежит дробное число в fixed-point представлении и нужно получить целую часть этого "дробного" в виде байта (отрицательные числа вернуть как 0, а всё что больше 255 вернуть как 255). C-функция делала битовое смещение в право, прибавляла константу и результат использовала как индекс в глобальном константном массиве, что бы получить на выход байт.
Я сначала конечно не поверил что такое простое дело будет работать быстрее чем if ... elif ... else но оказалось что всё таки немного быстрее работало. Видимо прочитать из кеша один байт быстрее чем пройтись по паре условных jmp-ов.
20 лет назад я такое делал.. в том числе и с fixed point. Такие масивчики на любую операцию делал, синусы, косинусы, квадраты, корни и т.д..
A🌚
linear probing и buckets - вот 2 основных подхода
Там ещё коллизии через random probing обрабатываются вроде бы
KK
20 лет назад я такое делал.. в том числе и с fixed point. Такие масивчики на любую операцию делал, синусы, косинусы, квадраты, корни и т.д..
Ну с синусами всё очевидно, а вот то что парочка простых условий работает медленнее чем обращение к массиву - не совсем очевидно.
БС
если надо часто делать такую операцию, то массив будет в кешлиниях, доступ к нему такт, а вот ветвления в современный супер скалярных процессорах зло. Если предсказатель ветвлений ошибся, то получаем пенальти. Контейнер очищается и начинается работа с начала. (мои знания об устройстве процов ограничивается третьими пентами, возможно в современных насовали больше логики, чтобы конвееры лучше работали.)
F
а кому-то удалось на mac big sur поставить pip_pypy3?
brew install gcc ставил?
VR
brew install gcc ставил?
да
VR
сам pypy3 поставился без проблем
VR
в совместимости написано что до catalina поддержка, наверное в этом дело)
A🌚
если надо часто делать такую операцию, то массив будет в кешлиниях, доступ к нему такт, а вот ветвления в современный супер скалярных процессорах зло. Если предсказатель ветвлений ошибся, то получаем пенальти. Контейнер очищается и начинается работа с начала. (мои знания об устройстве процов ограничивается третьими пентами, возможно в современных насовали больше логики, чтобы конвееры лучше работали.)
Принцип работы не поменялся, из-за него мы и получили нашумевшие спектр и мелтдаун