Русский
Русский
English
Статистика
Реклама

Массивы

Нативный не значит быстрый. Обгоняем map, filter и reduce на больших массивах

21.08.2020 10:13:31 | Автор: admin


Несколько дней назад я выкладывал пост LINQ на JavaScript для самых маленьких. Но моя библиотека сильно уступала по производительности нативным методам и Lodash. В общем-то, сейчас мы будем менять ситуацию.


Скажу сразу: в статье не будет каких-либо откровений, мы не будем строить безумные алгоритмы и т. д. Мы просто сравним производительность разных конструкций языка.


Когда я впервые выложил свою библиотеку в публичный доступ, у меня стоял вопрос лишь о том, чтобы удешевить итерацию нативного метода. Я старался облегчить callback, потому что у меня даже не возникало мысли, что map, filter или reduce могут быть даже чуточку медленнее, чем скорость света.


Прежде чем мы приступим



Поговорим о статистике


Мы будем проводить замеры следующих методов:


  • Нативный метод
  • Аналог написанный с помощью for of
  • Аналог написанный с помощью for
  • Аналогичный метод из библиотеки Lodash
  • Аналогичный метод из моей собственной библиотеки ursus-utilus-collections

Ахтунг!

Если вы посмотрите исходники, то увидите, что методы из моей библиотеки основаны сугубо на конструкции for.
Но я привожу здесь код с ними сугубо для того, чтобы похвастаться вы могли оценить как влияют на производительность дополнительные слои абстракции.

За замер производительности у нас будет отвечать Benchmark.js. Каждый пример проходил замеры 10 раз на массиве размером в 10,000,000 элементов.
Среда выполнения: Node.js.


Так с входными данными разобрались, теперь давайте обсудим то, что будет на выходе.


Я буду приводить пример кода и его наиболее средний бенчмарк.


В конце раздела я приведу таблицу с наиболее полной статистикой: с межквартильным средним и с медианным бенчмарками. И приведу весь бенчмарк-лог.


Приступим



Filter


Для замера производительности мы будем отфильтровывать все нечетные числа:


const filterCondition = (item: number) => !!(item % 2);

Нативная фильтрация


array.filter(filterCondition);

Benchmark
native filter x 3.58 ops/sec 5.48% (13 runs sampled)



For of


const result = [];for(let item of array) {    if(filterCondition(item)) {        result.push(item)    }}

Benchmark
for of x 3.48 ops/sec 3.46% (14 runs sampled)

Внимание, for of почти не уступает про производительности нативной фильтрации, но дальше больше.




For


filterSuite.add('for', () => {    const result = [];    for(let i = 0; i < array.length; i++) {        const item = array[i]        if(filterCondition(item)) {            result.push(item)        }    }})

Benchmark
for x 6.92 ops/sec 5.47% (20 runs sampled)

Обычный for обгоняет filter в 2 раза.




Lodash


Перейдем к игрокам на поле абстракций:


lodash(array).filter(filterCondition).value();

Benchmark
lodash filter x 3.60 ops/sec 4.13% (13 runs sampled)

Lodash по производительности не уступает filter.




Моя библиотека


ursus(array).where(filterCondition).toArray();

Benchmark
ursus where x 6.87 ops/sec 4.86% (20 runs sampled)

Моя реализация фильтра равна for, но незначительно медленнее.




Итоги


Benchmark log
lodash filter x 3.75 ops/sec 4.09% (13 runs sampled)native filter x 3.35 ops/sec 7.99% (13 runs sampled)for ... of x 3.38 ops/sec 3.88% (13 runs sampled)for x 6.04 ops/sec 3.54% (20 runs sampled)optimized for x 5.82 ops/sec 3.05% (20 runs sampled)ursus where x 5.83 ops/sec 4.62% (21 runs sampled)lodash filter x 3.37 ops/sec 3.40% (13 runs sampled)native filter x 3.33 ops/sec 4.76% (13 runs sampled)for ... of x 3.86 ops/sec 9.36% (14 runs sampled)for x 6.92 ops/sec 5.47% (20 runs sampled)optimized for x 6.96 ops/sec 4.22% (20 runs sampled)ursus where x 6.71 ops/sec 4.75% (19 runs sampled)lodash filter x 3.51 ops/sec 4.94% (13 runs sampled)native filter x 3.72 ops/sec 0.74% (13 runs sampled)for ... of x 3.54 ops/sec 2.14% (14 runs sampled)for x 6.84 ops/sec 4.60% (20 runs sampled)optimized for x 6.85 ops/sec 3.58% (19 runs sampled)ursus where x 6.46 ops/sec 11.83% (20 runs sampled)lodash filter x 3.55 ops/sec 6.26% (13 runs sampled)native filter x 3.66 ops/sec 3.06% (13 runs sampled)for ... of x 3.41 ops/sec 4.28% (14 runs sampled)for x 6.95 ops/sec 3.85% (20 runs sampled)optimized for x 6.79 ops/sec 4.33% (20 runs sampled)ursus where x 7.17 ops/sec 3.29% (21 runs sampled)lodash filter x 3.63 ops/sec 3.38% (13 runs sampled)native filter x 3.63 ops/sec 3.35% (13 runs sampled)for ... of x 3.44 ops/sec 3.99% (14 runs sampled)for x 6.89 ops/sec 4.53% (20 runs sampled)optimized for x 6.95 ops/sec 3.17% (20 runs sampled)ursus where x 6.87 ops/sec 4.86% (20 runs sampled)lodash filter x 3.60 ops/sec 4.13% (13 runs sampled)native filter x 3.58 ops/sec 5.48% (13 runs sampled)for ... of x 3.48 ops/sec 3.46% (14 runs sampled)for x 6.95 ops/sec 3.73% (20 runs sampled)optimized for x 6.78 ops/sec 5.62% (20 runs sampled)ursus where x 7.17 ops/sec 3.79% (21 runs sampled)lodash filter x 3.64 ops/sec 4.11% (13 runs sampled)native filter x 3.63 ops/sec 3.35% (13 runs sampled)for ... of x 3.55 ops/sec 2.36% (14 runs sampled)for x 6.91 ops/sec 4.51% (20 runs sampled)optimized for x 6.89 ops/sec 3.76% (20 runs sampled)ursus where x 7.03 ops/sec 4.84% (21 runs sampled)lodash filter x 3.59 ops/sec 4.17% (13 runs sampled)native filter x 3.60 ops/sec 3.14% (13 runs sampled)for ... of x 3.45 ops/sec 4.69% (14 runs sampled)for x 7.09 ops/sec 2.65% (20 runs sampled)optimized for x 6.81 ops/sec 2.90% (20 runs sampled)ursus where x 7.15 ops/sec 2.60% (21 runs sampled)lodash filter x 3.60 ops/sec 5.57% (13 runs sampled)native filter x 3.60 ops/sec 4.55% (13 runs sampled)for ... of x 3.39 ops/sec 7.33% (13 runs sampled)for x 5.71 ops/sec 2.74% (19 runs sampled)optimized for x 5.85 ops/sec 2.70% (20 runs sampled)ursus where x 6.10 ops/sec 2.43% (21 runs sampled)lodash filter x 3.18 ops/sec 5.88% (13 runs sampled)native filter x 3.34 ops/sec 4.43% (13 runs sampled)for ... of x 3.89 ops/sec 6.84% (14 runs sampled)for x 7.09 ops/sec 2.79% (21 runs sampled)optimized for x 6.70 ops/sec 3.32% (20 runs sampled)ursus where x 7.07 ops/sec 4.02% (20 runs sampled)

Межкв. Среднее Медиана
filter 3,57 ops/sec 3,60 ops/sec
for 3,48 ops/sec 3,47 ops/sec
for of 6,91 ops/sec 6,92 ops/sec
lodash 3,58 ops/sec 3,60 ops/sec
ursus 6,88 ops/sec 6,95 ops/sec

Результаты гонки:


1) For
2) Ursus
3) Lodash
4) Filter
5) For of


Map


Для тестирования мы будем прибавлять ко всем числам +1


const mapCondition = (item: number) => item + 1;

Нативное отображение


array.map(mapCondition);

Benchmark
native map x 0.68 ops/sec 3.60% (6 runs sampled)



For of


const result = [];for(let item of array) {    result.push(mapCondition(item))}

Benchmark
for of x 2.19 ops/sec 3.47% (10 runs sampled)

В случае отображения for of обгоняет нативный метод в 3 раза.




For


const result = [];for(let i = 0; i < array.length; i++) {    result.push(mapCondition(array[i]))}

Benchmark
for x 3.49 ops/sec 6.82% (12 runs sampled)

Классический for обгоняет нативный метод в 5 раз.




Lodash


lodash(array).map(mapCondition).value();

Benchmark
lodash map x 5.78 ops/sec 9.03% (18 runs sampled)

Lodash обходит всех в 9 раз!


Честно, разработчики какие-то волшебники, я не представляю как они такого добились.



Моя библиотека


ursus(array).select(mapCondition).toArray();

Benchmark
ursus select x 3.54 ops/sec 5.71% (13 runs sampled)

Каким-то образом моя реализация чуточку быстрее чем просто for, на котором она основана. _()_/


Итоги


Benchmark log
lodash map x 6.08 ops/sec 4.84% (19 runs sampled)native map x 0.57 ops/sec 17.60% (6 runs sampled)for ... of x 1.91 ops/sec 13.65% (9 runs sampled)for x 3.51 ops/sec 5.25% (13 runs sampled)optimized for x 3.62 ops/sec 7.49% (13 runs sampled)ursus select x 3.29 ops/sec 9.24% (13 runs sampled)lodash map x 5.59 ops/sec 10.61% (19 runs sampled)native map x 0.61 ops/sec 11.70% (6 runs sampled)for ... of x 2.30 ops/sec 2.13% (10 runs sampled)for x 3.72 ops/sec 4.39% (13 runs sampled)optimized for x 3.58 ops/sec 5.24% (13 runs sampled)ursus select x 3.58 ops/sec 5.21% (13 runs sampled)lodash map x 6.06 ops/sec 5.23% (19 runs sampled)native map x 0.68 ops/sec 3.60% (6 runs sampled)for ... of x 2.27 ops/sec 3.49% (10 runs sampled)for x 3.45 ops/sec 10.41% (13 runs sampled)optimized for x 3.59 ops/sec 4.29% (13 runs sampled)ursus select x 3.54 ops/sec 6.08% (12 runs sampled)lodash map x 5.81 ops/sec 7.23% (19 runs sampled)native map x 0.68 ops/sec 3.63% (6 runs sampled)for ... of x 2.31 ops/sec 7.11% (10 runs sampled)for x 3.62 ops/sec 4.74% (13 runs sampled)optimized for x 3.45 ops/sec 6.67% (13 runs sampled)ursus select x 3.64 ops/sec 4.42% (13 runs sampled)lodash map x 6.03 ops/sec 5.26% (20 runs sampled)native map x 0.69 ops/sec 6.27% (6 runs sampled)for ... of x 2.12 ops/sec 8.87% (10 runs sampled)for x 3.29 ops/sec 9.33% (13 runs sampled)optimized for x 3.53 ops/sec 5.18% (13 runs sampled)ursus select x 3.66 ops/sec 4.03% (13 runs sampled)lodash map x 5.78 ops/sec 9.03% (18 runs sampled)native map x 0.65 ops/sec 6.52% (6 runs sampled)for ... of x 2.07 ops/sec 7.41% (10 runs sampled)for x 3.49 ops/sec 6.82% (12 runs sampled)optimized for x 3.50 ops/sec 5.93% (13 runs sampled)ursus select x 3.54 ops/sec 5.71% (13 runs sampled)lodash map x 5.68 ops/sec 8.47% (18 runs sampled)native map x 0.67 ops/sec 6.40% (6 runs sampled)for ... of x 2.11 ops/sec 5.06% (10 runs sampled)for x 3.52 ops/sec 5.58% (13 runs sampled)optimized for x 3.29 ops/sec 5.51% (13 runs sampled)ursus select x 3.38 ops/sec 5.31% (13 runs sampled)lodash map x 6.37 ops/sec 3.10% (19 runs sampled)native map x 0.67 ops/sec 2.43% (6 runs sampled)for ... of x 2.19 ops/sec 3.47% (10 runs sampled)for x 3.41 ops/sec 8.13% (13 runs sampled)optimized for x 3.54 ops/sec 5.15% (13 runs sampled)ursus select x 3.53 ops/sec 6.28% (13 runs sampled)lodash map x 5.85 ops/sec 11.04% (19 runs sampled)native map x 0.66 ops/sec 4.30% (6 runs sampled)for ... of x 2.20 ops/sec 2.97% (10 runs sampled)for x 3.45 ops/sec 8.03% (13 runs sampled)optimized for x 3.48 ops/sec 5.13% (13 runs sampled)ursus select x 3.68 ops/sec 3.33% (13 runs sampled)lodash map x 5.31 ops/sec 12.87% (18 runs sampled)native map x 0.68 ops/sec 4.26% (6 runs sampled)for ... of x 2.11 ops/sec 6.97% (10 runs sampled)for x 3.35 ops/sec 6.12% (13 runs sampled)optimized for x 3.38 ops/sec 5.55% (13 runs sampled)ursus select x 3.54 ops/sec 6.20% (13 runs sampled)

Межкв. Среднее Медиана
map 0.67 ops/sec 0.67 ops/sec
for 2.17 ops/sec 2.16 ops/sec
for of 3.47 ops/sec 3.47 ops/sec
lodash 5.79 ops/sec 5.80 ops/sec
ursus 3.56 ops/sec 3.54 ops/sec

Результаты гонки:


1) Lodash
2) Ursus
3) For
4) For of
5) Map


Reduce


Свертку мы будем тестировать на суммировании элементов


const sumCondition = (item1: number, item2: number) => item1 + item2;

Нативная свертка


array.reduce(sumCondition);

Benchmark
native reduce x 6.09 ops/sec 9.13% (20 runs sampled)



For of


Пропускает гонку, так как я не придумал как его можно приладить без операций с массивом. А с ними замеры уже будут не такие объективные.



For


let result = array[0];for(let i = 1; i < array.length; i++) {    result = sumCondition(result, array[i])}

Benchmark
for x 57.01 ops/sec 2.53% (59 runs sampled)

For обходит нативный метод почти в 10 раз!




Lodash


lodash(array).sum();

Benchmark
lodash sum x 8.30 ops/sec 7.79% (25 runs sampled)

А вот lodash подкачал, он почти такой же, как и reduce.




Моя библиотека


ursus(array).sum(sumCondition);

Benchmark
ursus sum x 56.12 ops/sec 2.38% (58 runs sampled)

Итоги


Benchmark log
lodash sum x 8.60 ops/sec 4.35% (25 runs sampled)native reduce x 6.69 ops/sec 3.73% (21 runs sampled)for x 68.67 ops/sec 3.41% (70 runs sampled)optimized for x 70.75 ops/sec 2.63% (72 runs sampled)ursus sum x 67.78 ops/sec 3.12% (70 runs sampled)lodash sum x 9.00 ops/sec 3.93% (26 runs sampled)native reduce x 5.47 ops/sec 21.31% (19 runs sampled)for x 56.61 ops/sec 2.70% (59 runs sampled)optimized for x 56.85 ops/sec 2.27% (59 runs sampled)ursus sum x 56.08 ops/sec 2.40% (59 runs sampled)lodash sum x 8.69 ops/sec 3.36% (26 runs sampled)native reduce x 6.09 ops/sec 9.13% (20 runs sampled)for x 57.01 ops/sec 2.53% (59 runs sampled)optimized for x 57.38 ops/sec 2.64% (60 runs sampled)ursus sum x 56.12 ops/sec 2.38% (58 runs sampled)lodash sum x 8.68 ops/sec 4.11% (26 runs sampled)native reduce x 6.06 ops/sec 9.39% (19 runs sampled)for x 69.97 ops/sec 2.82% (71 runs sampled)optimized for x 66.55 ops/sec 4.16% (68 runs sampled)ursus sum x 69.29 ops/sec 2.73% (71 runs sampled)lodash sum x 7.86 ops/sec 8.39% (24 runs sampled)native reduce x 6.35 ops/sec 4.79% (20 runs sampled)for x 55.91 ops/sec 5.01% (58 runs sampled)optimized for x 56.41 ops/sec 2.70% (59 runs sampled)ursus sum x 57.11 ops/sec 2.16% (58 runs sampled)lodash sum x 8.11 ops/sec 4.72% (24 runs sampled)native reduce x 5.97 ops/sec 7.80% (20 runs sampled)for x 56.43 ops/sec 3.62% (59 runs sampled)optimized for x 56.87 ops/sec 3.75% (59 runs sampled)ursus sum x 55.37 ops/sec 3.60% (58 runs sampled)lodash sum x 8.52 ops/sec 6.70% (25 runs sampled)native reduce x 6.12 ops/sec 7.39% (20 runs sampled)for x 57.96 ops/sec 3.50% (58 runs sampled)optimized for x 55.19 ops/sec 5.32% (59 runs sampled)ursus sum x 56.75 ops/sec 3.33% (58 runs sampled)lodash sum x 8.00 ops/sec 8.94% (25 runs sampled)native reduce x 5.75 ops/sec 6.95% (19 runs sampled)for x 56.78 ops/sec 4.21% (57 runs sampled)optimized for x 56.89 ops/sec 2.32% (60 runs sampled)ursus sum x 54.61 ops/sec 7.04% (57 runs sampled)lodash sum x 8.11 ops/sec 8.83% (24 runs sampled)native reduce x 5.97 ops/sec 7.84% (19 runs sampled)for x 57.32 ops/sec 4.17% (59 runs sampled)optimized for x 55.97 ops/sec 4.18% (59 runs sampled)ursus sum x 55.76 ops/sec 3.90% (58 runs sampled)lodash sum x 8.30 ops/sec 7.79% (25 runs sampled)native reduce x 6.31 ops/sec 5.42% (20 runs sampled)for x 55.45 ops/sec 5.56% (58 runs sampled)optimized for x 57.54 ops/sec 3.52% (59 runs sampled)ursus sum x 55.22 ops/sec 4.34% (57 runs sampled)

Межкв. Среднее Медиана
reduce 6.09 ops/sec 6.08 ops/sec
for 57.02 ops/sec 56.90 ops/sec
lodash 8.39 ops/sec 8.41 ops/sec
ursus 56.20 ops/sec 56.10 ops/sec

Результаты гонки:


1) For
2) Ursus
3) Lodash
4) Reduce


Заключение


Как вы могли увидеть, на 10 миллионном массиве нативные реализации работают в разы медленнее, чем for и библиотечные реализации.


В общем-то, нативная реализация начинает обгонять lodash на 50k элементов в массиве и меньше.

А на 25k начинает обгонять даже for.

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


Спасибо за внимание!

Подробнее..

Модификация исполняемого кода как способ реализации массивов с изменяемым границами

09.01.2021 02:10:27 | Автор: admin

Введение

В свете все возрастающего потока англоязычных околонаучных терминов в области программирования и следуя за модой, в названии статьи можно было бы вместо некрасивого модификация исполняемого кода написать что-нибудь вроде run-time reflection. Суть от этого не меняется. Речь о реализации в компиляторе такого непростого объекта, как массив с заранее неизвестными границами. Типичный пример использования подобных объектов это операции (в математическом смысле) с матрицами разных размеров.

В данном случае имеется в виду многомерный массив, который занимает непрерывный участок памяти и у которого границы задаются уже при работе программы, причем нижние границы не обязательно начинаются с нуля. Реализация обращения к таким массивам гораздо сложнее случая границ-констант, известных при компиляции.

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

Из сложности реализации таких массивов следует неприятное следствие: обращение к массивам с динамическими границами выполняется существенно медленнее, чем к массивам с границами-константами. Желательно было бы соединить мощь и удобство работы с массивами с задаваемыми при исполнении кода границами с быстротой доступа к массивам с границами-константами, когда часть вычислений адресов элементов может производиться уже на этапе компиляции программы.

Далее все рассуждения приводятся на примере конкретной реализации компилятора PL/1-KT с языка PL/1 для Win64.

Подход к реализации

Самый простой подход к решению данной задачи, который первым приходит в голову заменить значения границ-констант массивов на новые нужные значения и просто перетранслировать программу. Разумеется, во многих случаях такой подход неприемлем. Но рассмотрим, чем будет отличаться выполняемый код? Например, такому обращению к элементу массива:

dcl x(100,100) float(53);dcl (i,j)      fixed(63);x(i,j)=12345e0;

соответствует такой исполняемый код x86-64:

48693DB838010020030000   imul rdi,I,80048A1C038010000000000     mov  rax,J488DBCC710FDFFFF         lea  rdi,X+0FFFFFCD8h[rdi+rax*8]BE30000000               mov  rsi,offset @00000030h48A5                     movsq

Видно, что при разных значениях границ-констант массива исполняемый код будет отличаться лишь разными значениями операндов-констант в некоторых командах. В данном случае это значение третьего операнда-константы операции IMUL и константа-смещение в операции LEA.

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

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

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

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

Выделение памяти для массивов с динамическими границами

Если границы массивов, а, значит, и объем занимаемой памяти, меняются во время исполнения программы, то в общем случае такие массивы не могут размещаться в статической памяти. Конечно, там можно заранее разместить массив с заведомо наибольшими значениями границ, а затем в процессе исполнения только динамически уменьшать их, но такой подход ограничен и неудобен.

Поэтому память для массивов с динамическими границами должен явно выделять программист из кучи оператором ALLOCATE и освобождать оператором FREE. В языке PL/1 такие объекты считаются объектами с управляемой (CONTROLLED) памятью.

Следовательно, новые значения констант должны быть определены до собственно создания массива, т.е. до выполнения соответствующего оператора ALLOCATE. Поэтому и обращение к служебной подпрограмме замены констант для данного массива должно быть тоже прежде выполнения оператора ALLOCATE, так как объем выделяемой для массива памяти это также операнд-константа в одной из команд перед вызовом ALLOCATE, зависящий от размеров границ.

Обработка констант

Константы, которые вычисляются из границ-констант массива и которые, в конечном итоге, становятся частью операндов-констант исполняемого кода, формируются на этапе анализа исходного текста программы при компиляции.

Компилятор PL/1-KT переводит текст программы в промежуточную обратную польскую запись, где каждая константа это отдельная операция, имеющая единственный операнд само значение константы (4 байта). Для реализации динамических массивов вводится новая операция модифицированная константа, которая имеет не значение, а операнд-ссылку на таблицу компилятора. По ссылке располагается само значение константы, а также вся необходимая информация, позволяющая определить, как получилось данное значение, и, следовательно, позволяющая рассчитать новое значение при новых границах.

После окончания трансляции эти ссылки сохраняются и в выполняемом модуле, причем к ним добавляются адреса команд, в код которых замешивается данная константа, а также адрес служебного (создаваемого компилятором) указателя на выделенную динамическому массиву память.

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

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

Объекты программы, зависящие от размеров границ массивов

Таких объектов в программе на языке PL/1 оказалось восемь:

- встроенные функции языка LBOUND/HBOUND/DIMENSION, выдающие значения нижней/верхней границы или числа элементов для заданной размерности;

- оператор ALLOCATE, неявно имеющий входным параметром число выделяемых массиву байт, зависящее от его границ;

- индекс, т.е. собственно команды вычисляющие часть адреса по очередному индексу-переменной при обращении к элементу массива;

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

- смещение массива, это последняя из команд вычисления адреса элемента массива. К этому моменту уже вычислены составляющие адреса от индексов-переменных и в этой команде для x86-64 обычно реализуется базово-индексный режим адресации, причем в команде имеется постоянное смещение, которое как раз и зависит от значений границ и должно быть скорректировано. Ненулевое смещение возникает, так как нижние границы не обязательно нулевые, некоторые индексы могут быть константами, а элемент, адрес которого вычисляется, сам может быть элементом структуры (агрегата разнотипных элементов), имеющим свое постоянное смещение - начало каждого элемента внутри этой структуры;

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

Наиболее громоздким для обработки является корректировка константы в команде элемента смещение, поскольку в константу команды-смещение входят и части от индексов-констант. Служебной подпрограмме необходимо повторить весь расчет адресной части заново, причем, если по дороге были индексы-константы, еще необходимо тут же проверить их на выход за пределы новых значений границ.

Синтаксис массивов с изменяемыми границами

В стандарте языка PL/1 изменяемые границы массивов просто задаются выражениями, например:

dcl  n      fixed(31),     x(0:n) float ctl;get list(n);allocate x;

Для описываемой реализации такая запись бессмысленна, поскольку границы будут меняться другим способом, поэтому в описании вместо переменных используется знак *, этот пример эквивалентен предыдущему:

dcl  n      fixed(31),     x(*)   float ctl;get list(n);?index(1,1)=0; ?index(1,2)=n; // устанавливаем новые границыcall ?ret(addr(x));           // меняем константы кода обращения к xallocate x;

Для изменения границ в компилятор PL/1-KT введены служебные элементы в виде встроенного глобального двумерного массива новых значений нижних и верхних границ:

dcl ?index(15,2) fixed(31) external;

Первая размерность этого массива 1:15, поскольку это максимально допустимое число размерностей массива в компиляторе PL/1-KT.

А также введена служебная подпрограмма перетрансляции, т.е. корректировки констант в командах, использующая текущие значения массива ?index:

dcl ?ret entry(ptr) external;

Служебный массив ?index и подпрограмма ?ret предопределены в компиляторе PL/1-KT. При запуске программы все значения границ в массиве ?index по умолчанию заданы единичными.

Передача новых значений границ через глобальный массив ?index, а не через входные параметры подпрограммы ?ret сделана для большей гибкости их использования. Например, в этом случае не требуется повторять задания границ для массивов одинаковых размеров, не требуется каждый раз перечислять нижние границы каждой размерности, если они всегда остаются единичными и т.п.

В случае какой-либо ошибки корректировки констант, эта подпрограмма не возвращает код ошибки, но инициирует перехватываемое исключение, поскольку далее обращение к массиву, указанному как входной параметр, даст непредсказуемые результаты.

Компилятор PL/1-KT отмечает в своей таблице признак изменяемой границы у данного массива, а сам значок * просто заменяет на некоторые некруглые значения границ. Это сделано для того, чтобы далее в процессе компиляции создавались обычные команды для массивов с границами-константами. А некруглые значения не позволяют оптимизатору применять более короткие формы команд, поскольку тогда невозможно скорректировать их другими, например, большими значениями.

Динамические границы, обозначаемые *, могут быть только старшими размерностями и следовать подряд. При этом такие границы могут быть не только у массивов однородных элементов, но и у массивов структур, т.е. агрегатов данных разных типов. Младшие размерности при этом могут оставаться константами, например:

dcl // структура-массив с изменяемыми границами1 s(*,*)       ctl, 2 x1          char(100) var, 2 y1 (-1:25)  float, // внутри могут быть и границы-константы 2 z1 (100)    fixed(31);

Ссылка на массивы с изменяемыми границами

Для передачи в подпрограммы массивов с изменяемыми границами как параметров, учитывается тот факт, что такие массивы всегда неявно используют указатели. Но поскольку это служебные указатели, создаваемые компилятором, напрямую использовать их имена нельзя. Обращение к указателю без явного использования его имени возможно в языке PL/1 в случае применения встроенной функции ADDR, например:

dcl x(100) float based(p1),   (p1,p2) ptr;p2=addr(x); //это эквивалентно p2=p1;

Таким образом, если нужно передавать как параметры массивы с динамическими границами, достаточно передать указатели на них с помощью ADDR, без явного использования имен служебных указателей:

call умножение_матриц(addr(a),addr(b),addr(c),m,n,q);

и тогда описание параметров таких подпрограмм становится единообразным, не зависящим от самих массивов:

dcl умножение_матриц entry(ptr,ptr,ptr,fixed(31),fixed(31),fixed(31));

Этот прием позволяет передавать динамические массивы в подпрограммы, но не позволяет принимать их внутри подпрограмм, поскольку тогда опять нужно присваивать указатели-параметры служебным указателям с недоступными именами. Поэтому в компиляторе PL/1-KT дополнительно разрешено использовать и в левой части присваивания встроенную функцию ADDR:

dcl x(*) float ctl,    p1   ptr;addr(x)=p1; //эквивалентно оператору <служебный указатель на x>=p1;

Пример использования динамических массивов как параметров

В данном примере применена описанная выше технология корректировки констант для универсального умножения матриц задаваемого размера. Динамические массивы-матрицы создаются оператором ALLOCATE и передаются (неявно, указателями) в универсальную процедуру умножения матриц. Корректировка констант в исполняемом коде производится как для фактических параметров A1, B1,C1, так и для формальных A, B, C внутри подпрограммы. Кроме этого, формальным параметрам присваиваются фактические значения с помощью разрешения использовать функцию ADDR в левой части присваивания. Процедура УМНОЖЕНИЕ_МАТРИЦ может находиться в отдельном модуле и транслироваться автономно.

TEST:PROC MAIN;DCL (A1,B1,C1)(*,*) FLOAT CTL; // ДИНАМИЧЕСКИЕ МАТРИЦDCL (M1,N1,Q1)      FIXED(31); // ЗАДАВАЕМЕ ГРАНИЦDCL (I,J)           FIXED(31); // РАБОЧИЕ ПЕРЕМЕННЕ//---- ДЛЯ ТЕСТА ЗАДАЕМ НЕКОТОРЕ ЗНАЧЕНИЯ ГРАНИЦ ----M1=5; N1=4; Q1=3;//---- КОРРЕКТИРУЕМ КОНСТАНТ A1(M1,N1), B1(N1,Q1), C1(M1,Q1) ----?INDEX(1,2)=M1; ?INDEX(2,2)=N1;?RET(ADDR(A1));                   // ИЗМЕНЯЕМ КОМАНД ДЛЯ A1?INDEX(1,2)=N1; ?INDEX(2,2)=Q1;?RET(ADDR(B1));                   // ИЗМЕНЯЕМ КОМАНД ДЛЯ B1?INDEX(1,2)=M1;?RET(ADDR(C1));                   // ИЗМЕНЯЕМ КОМАНД ДЛЯ C1//---- СОЗДАЕМ МАТРИЦ A1(M1,N1), B1(N1,Q1) И C1(M1,Q1) ----ALLOCATE A1,B1,C1;//---- ДЛЯ ТЕСТА ЗАПОЛНЯЕМ МАТРИЦ НЕКОТОРМИ ЗНАЧЕНИЯМИ ----DO I=1 TO M1; DO J=1 TO N1; A1(I,J)=I+J; END J; END I;DO I=1 TO N1; DO J=1 TO Q1; B1(I,J)=I-J; END J; END I;//---- УМНОЖЕНИЕ МАТРИЦ A1 И B1, РЕЗУЛЬТАТ - МАТРИЦА C1 ----УМНОЖЕНИЕ_МАТРИЦ(ADDR(A1),ADDR(B1),ADDR(C1),M1,N1,Q1);//---- ВДАЕМ ПОЛУЧЕННЙ РЕЗУЛЬТАТ ----PUT SKIP DATA(C1);FREE A1,B1,C1;//========== УМНОЖЕНИЕ МАТРИЦ ЗАДАННОГО РАЗМЕРА ==========УМНОЖЕНИЕ_МАТРИЦ:PROC(P1,P2,P3,M,N,Q);//---- ВХОД A(M,N) И B(N,Q), ОТВЕТ - МАТРИЦА C(M,Q) ----DCL (P1,P2,P3)   PTR;       // УКАЗАТЕЛИ НА МАТРИЦDCL (M,N,Q)      FIXED(31); // ЗАДАННЕ ГРАНИЦDCL (A,B,C)(*,*) FLOAT CTL; // ДИНАМИЧЕСКИЕ МАТРИЦDCL (I,J,K)      FIXED(31); // РАБОЧИЕ ПЕРЕМЕННЕ//---- НОВЕ ОПЕРАТОР ПРИСВАИВАНИЯ УКАЗАТЕЛЕЙ ----ADDR(A)=P1;     // АДРЕС ДЛЯ МАССИВА AADDR(B)=P2;     // АДРЕС ДЛЯ МАССИВА BADDR(C)=P3;     // АДРЕС ДЛЯ МАССИВА C//---- КОРРЕКТИРУЕМ КОНСТАНТ МАТРИЦ A(M,N), B(N,Q), C(M,Q) ----?INDEX(1,2)=M; ?INDEX(2,2)=N;?RET(ADDR(A));                    // ИЗМЕНЯЕМ КОМАНД ДЛЯ A?INDEX(1,2)=N; ?INDEX(2,2)=Q;?RET(ADDR(B));                    // ИЗМЕНЯЕМ КОМАНД ДЛЯ B?INDEX(1,2)=M;?RET(ADDR(C));                    // ИЗМЕНЯЕМ КОМАНД ДЛЯ C//---- САМО УМНОЖЕНИЕ МАТРИЦ ----DO I=1 TO M;   DO J=1 TO Q;          C(I,J)=0;          DO K=1 TO N;                 C(I,J)+=A(I,K)*B(K,J);          END K;   END J;END I;END УМНОЖЕНИЕ_МАТРИЦ;END TEST;

Эта тестовая программа эквивалентна приведенной ниже программе с обычными границами-константами у матриц.

TEST:PROC MAIN;DCL (P1,P2,P3)      PTR;             // УКАЗАТЕЛИ НА МАТРИЦDCL A1(5,4)         FLOAT BASED(P1), // СТАТИЧЕСКАЯ МАТРИЦА А1    B1(4,3)         FLOAT BASED(P2), // СТАТИЧЕСКАЯ МАТРИЦА B1    C1(5,3)         FLOAT BASED(P3); // СТАТИЧЕСКАЯ МАТРИЦА C1DCL (M1,N1,Q1)      FIXED(31);       // ЗАДАВАЕМЕ ГРАНИЦDCL (I,J)           FIXED(31);       // РАБОЧИЕ ПЕРЕМЕННЕ//---- ДЛЯ ТЕСТА ЗАДАЕМ НЕКОТОРЕ ЗНАЧЕНИЯ ГРАНИЦ ----M1=5; N1=4; Q1=3;//---- СОЗДАЕМ МАТРИЦ A1(M1,N1), B1(N1,Q1), C1(M1,Q1) ----ALLOCATE A1,B1,C1;//---- ДЛЯ ТЕСТА ЗАПОЛНЯЕМ МАТРИЦ НЕКОТОРМИ ЗНАЧЕНИЯМИ ----DO I=1 TO M1; DO J=1 TO N1; A1(I,J)=I+J; END J; END I;DO I=1 TO N1; DO J=1 TO Q1; B1(I,J)=I-J; END J; END I;//---- УМНОЖЕНИЕ МАТРИЦ A1 И B1, РЕЗУЛЬТАТ - МАТРИЦА C1 ----УМНОЖЕНИЕ_МАТРИЦ(ADDR(A1),ADDR(B1),ADDR(C1),M1,N1,Q1);//---- ВДАЕМ ПОЛУЧЕННЙ РЕЗУЛЬТАТ ----PUT SKIP DATA(C1);FREE A1,B1,C1;//========== УМНОЖЕНИЕ МАТРИЦ ЗАДАННОГО РАЗМЕРА ==========УМНОЖЕНИЕ_МАТРИЦ:PROC(P1,P2,P3,M,N,Q);//---- ВХОД A(M,N) И B(N,Q), ОТВЕТ - МАТРИЦА C(M,Q) ----DCL (P1,P2,P3)   PTR;             // УКАЗАТЕЛИ НА МАТРИЦDCL (M,N,Q)      FIXED(31);       // ЗАДАННЕ ГРАНИЦDCL A(5,4)       FLOAT BASED(P1), // СТАТИЧЕСКИЕ МАТРИЦ    B(4,3)       FLOAT BASED(P2),    C(5,3)       FLOAT BASED(P3);DCL (I,J,K)      FIXED(31);       // РАБОЧИЕ ПЕРЕМЕННЕ//---- САМО УМНОЖЕНИЕ МАТРИЦ ----DO I=1 TO M;   DO J=1 TO Q;          C(I,J)=0;          DO K=1 TO N;                 C(I,J)+=A(I,K)*B(K,J);          END K;   END J;END I;END УМНОЖЕНИЕ_МАТРИЦ;END TEST;

Обе программы дают идентичный результат:

C1(1,1)=  2.600000E+01 C1(1,2)=  1.200000E+01 C1(1,3)= -2.000000E+00C1(2,1)=  3.200000E+01 C1(2,2)=  1.400000E+01 C1(2,3)= -4.000000E+00C1(3,1)=  3.800000E+01 C1(3,2)=  1.600000E+01 C1(3,3)= -6.000000E+00C1(4,1)=  4.400000E+01 C1(4,2)=  1.800000E+01 C1(4,3)= -8.000000E+00C1(5,1)=  5.000000E+01 C1(5,2)=  2.000000E+01 C1(5,3)= -1.000000E+01

Заключение

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

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

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

В чем-то похожие подходы применялись и ранее, например, в языке Visual Basic имеется операция reDim, задающая границы при исполнении программы. Однако в этих случаях динамически меняются все же данные в программе, а не операнды команд ее исполняемого кода.

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

Послесловие

Обращаю внимание гг. комментаторов, что утверждение: это никому не нужно, поскольку наш компилятор создает прекрасные динамические массивы некорректно. Корректно оно в виде мне и моим коллегам по проекту это не нужно. В этом случае я рад за вас, но считаю, что радовать остальных читателей такими комментариями необязательно.

Подробнее..

Перевод Трюки с виртуальной памятью

15.01.2021 18:06:16 | Автор: admin

Я уже довольно давно хотел написать пост о работе с виртуальной памятью. И когда @jimsagevid в ответ на мой твит написал о ней, я понял, что время пришло.

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

Но, оказывается, с помощью виртуальной памяти можно делать довольно интересные вещи.

Неприлично большой массив

Напомню, что у меня был пост, где я описывал проблему с большой таблицей, отображающей идентификаторы объектов в указатели. Также я хотел зафиксировать эту таблицу в памяти, чтобы писатели могли атомарно изменять указатели в ней, не мешая читателям. Это означает, что использование чего-то вроде std::vector было невозможным, так как его внутренние структуры изменяются при увеличении размера вектора.

Создать массив фиксированного размера очень просто:

objecto *objects[MAXOBJECTS]

Но какой размер массива следует использовать? Если выбрать большое значение, то зря потратим память. Сделать массив небольшим нам его может не хватить. В упомянутом выше посте я использовал иерархический подход, но, как подсказал @jimsagevid, вместо этого можно использовать виртуальную память и избежать сложностей с иерархией таблиц.

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

Итак, в данной ситуации мы можем просто выбрать достаточно большое число для размера массива и виртуально выделить под него память. Например, 1 миллиард объектов:

#define MAXOBJECTS 1000000000ULLobjecto **objects = virtualalloc(MAXOBJECTS * sizeof(objecto ));

Мы используем 8 ГБ адресного пространства и виртуальной памяти, но физической только столько, сколько нам действительно нужно для наших объектов. Очень простое решение, для которого потребовалась всего одна строчка кода.

Примечание Я использую здесь условный virtualalloc() в качестве системного вызова для выделения виртуальной памяти, не зависящего от ОС. На самом деле в Windows вы бы вызвали VirtualAlloc(), а в Linux mmap().

Еще одно примечание Windows разделяет выделение виртуальной памяти на отдельные вызовы MEMRESERVE и MEMCOMMIT. MEMRESERVE резервирует адресное пространство, а MEMCOMMIT выделяет его в физической памяти. Но это не значит, что физическая память реально выделяется при вызове MEMCOMMIT, физическая память не выделяется, пока вы не обратитесь к страницам. MEMCOMMIT резервирует память в файле подкачки, а если вы попытаетесь выделить больше памяти, чем доступно в файле подкачки, то MEMCOMMIT завершится ошибкой. Поэтому в Windows вы, скорее всего, не будете использовать MEMCOMMIT для всей таблицы из моего примера (потому что у файла подкачки размер ограничен). Вместо этого лучше сначала использовать MEMRESERVE для всей таблицы, а затем MEMCOMMIT только для фактически используемого диапазона.

В отличие от этого, Linux допускает overcommit (чрезмерное выделение памяти). То есть вы можете выделить больше памяти, чем доступно в файле подкачки. По этой причине Linux не нуждается в отдельных операциях резервирования (reserve) и подтверждения (commit), что упрощает использование виртуальной памяти.

Есть ли проблема в резервировании виртуальной памяти для массива в 8 ГБ? Здесь два ограничения. Первое это адресное пространство. В 64-битном приложении адресное пространство составляет 264. Это очень большое число, в котором можно разместить миллиарды массивов гигабайтного размера. Второе ограничение касается виртуальной памяти. Операционная система обычно не позволяет выделять все возможное адресное пространство. Например, в 64-битной Windows мы можем выделить только 256 ТБ виртуальной памяти. Тем не менее в этом объеме можно разместить 32 000 массивов по 8 ГБ каждый, так что пока мы не совсем сходим с ума, все будет в порядке.

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

Вспомните об олдскульном способе писать игры на Си с использованием статических массивов:

uint32t numtanks;tankt tanks[MAXTANKS];uint32C11Cbullets;bulletC12CBULLETS];

Если вы пишете подобный код, то будьте уверены, что найдутся те, кто его будет критиковать, так как здесь есть ограничения на количество объектов. Выглядит забавно, но можно вместо использования std::vector просто избавиться от MAXC13C и выделить 1 ГБ виртуальной памяти для каждого из массивов:

#define GB 1000000000uint32_t num_tanks;tank_t *tanks = virtual_alloc(GB);uint32_t num_bullets;bullet_t *bullets = virtual_alloc(GB);

Уникальные ID в рамках всего приложения

Многим игровым движкам требуются уникальные идентификаторы (ID) для идентификации объектов. Часто код выглядит примерно так:

uint64_t allocate_id(system_t *sys){    return sys->next_free_id++;} 

Но с использованием виртуальной памяти можно сделать по другому. Вместо использования в качестве идентификаторов целых чисел будем использовать адреса, зарезервированные в виртуальной памяти. Это позволит нам создавать уникальные идентификаторы не только в текущей системе, но и глобально во всем приложении. А поскольку мы никогда не используем память, на которую указывают эти адреса, то физическая память не будет потребляться.

Это может выглядеть примерно так:

system_id_t *allocate_id(system_t *sys){    if (!sys->id_block || sys->id_block_used == PAGE_SIZE) {        sys->id_block = virtual_alloc(PAGE_SIZE);        sys->id_block_used = 0;    }    return (system_id_t *)(sys->id_block + sys->id_block_used++);}

Обратите внимание, что, используя для идентификатора указатель на непрозрачную структуру (opaque struct), мы также получаем некоторую безопасность типа, которой у нас не было с uint64_t.

Обнаружение перезаписи памяти

Один из самых сложных багов для исправления это случайная перезапись памяти, когда какой-то код пишет в участок памяти, в который он не должен писать. Когда позже какой-нибудь другой код попытается использовать эту память, то он прочитает там мусор и, скорее всего, упадет. Проблема здесь заключается в том, что хотя само по себе падение найти легко, но сложно определить, где изначально произошла неправильная запись, повредившая данные. К счастью, виртуальная память может помочь нам и здесь.

Чтобы понять как, давайте сначала обратим внимание на то, что термин "случайная перезапись памяти" на самом деле неправильный. Адресное пространство в основном пустое. При 64-битном адресном пространстве и размере приложения, скажем, 2 ГБ, адресное пространство пусто на 99,999999988%. Это означает, что если перезапись памяти действительно случайная, то, скорее всего, она попала бы в это пустое пространство, что привело бы к ошибке/нарушению доступа к странице. А это бы привело к падению приложения в момент некорректной записи, а не при невинном чтении, что бы значительно упростило поиск и исправление ошибки.

Но, конечно, обычно запись не бывает абсолютно случайной. Вместо этого она часто попадает в одну из двух категорий:

  • Запись в память, которая была освобождена.

  • Запись за пределами выделенной памяти для объекта.

В обоих случаях весьма вероятно, что запись действительно попадет в какой-то другой объект, а не в пустое место. В первом случае память, скорее всего, предназначалась для чего-то другого. А во втором запись, вероятно, попадет в соседний объект или заголовок блока распределения (allocation block header).

Мы можем сделать это более случайным, заменив стандартный системный аллокатор на end-of-page аллокатор (аллокатор в конце страницы). Такой аллокатор размещает каждый объект в виртуальной памяти в собственном множестве страниц и выравнивает объект так, чтобы он располагался в конце блока памяти.

Размещение блока в конце блока страниц.Размещение блока в конце блока страниц.

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

Во-вторых, так как конец блока совпадает с концом страницы, запись за пределы конца блока также приведет к нарушению доступа. Другими словами, при таком подходе наши попытки "ошибочной" записи в память будут завершаться ошибкой в момент записи, что позволит нам легко обнаружить проблему.

Так как такой аллокатор округляет выделение памяти по размеру страницы, то для небольших данных будет тратиться лишняя память. Поэтому обычно я работаю со стандартным аллокатором, но если подозреваю, что происходит перезапись памяти, то переключаюсь на end-of-page аллокатор. После устранения проблемы я переключаюсь обратно на стандартный аллокатор. Конечно, возможность переключения аллокатора должна быть заложена в архитектуру вашего проекта.

Написание end-of-page аллокатора совсем несложно. Вот как может выглядеть malloc:

void *eop_malloc(uint64_t size){    uint64_t pages = (size + PAGE_SIZE - 1) / PAGE_SIZE;    char *base = virtual_alloc(pages * PAGE_SIZE);    uint64_t offset = pages * PAGE_SIZE - size;    return base + offset;}

Примечание Здесь все еще остается вероятность порчи данных при записи. Например, после очистки страниц выделение памяти для новой страницы может произойти в том же диапазоне. Кроме того, есть вероятность, что другой набор страниц может быть расположен в памяти непосредственно после нашего, и в этом случае мы не обнаружим перезапись за пределами последней страницы.

Обе эти проблемы можно исправить. Для решения первой проблемы мы можем оставить страницы зарезервированными (reserved), но не подтвержденными (commited). Таким образом, физическая память освобождается и мы получим ошибки страниц, но адреса остаются зарезервированными и не смогут использоваться другими объектами. Для второй проблемы можно зарезервировать дополнительную страницу после наших страниц, но не подтверждать ее. Тогда никакой другой объект не сможет претендовать на эти адреса и запись в них все равно приведет к ошибке доступа (access violation). (Примечание: это работает только в Windows, где reserve и commit являются отдельными операциями.)

Однако на практике мне никогда не приходилось принимать эти дополнительные меры предосторожности. Для меня всегда было достаточно обычного end-of-page аллокатора.

Непрерывное выделение памяти

В былые времена фрагментация памяти могла стать ночным кошмаром для программистов. Но и на современных машинах фрагментация памяти может стать большой проблемой при попытке реализации эффективных аллокаторов памяти.

Аллокатор памяти запрашивает у системы большие куски памяти и по запросу пользователя разбивает их на более мелкие фрагменты. Фрагментация памяти происходит, когда освобождается только часть из них, оставляя дыры в используемом блоке памяти.

Фрагментация памяти.Фрагментация памяти.

Проблема здесь в том, что когда пользователь запрашивает большой объем памяти, то может оказаться, что ни в одной из "дыр" не будет достаточно места. Это означает, что мы должны выделить память из свободного блока в конце, увеличивая использование памяти. Другими словами, появляется много впустую потраченной памяти, которую мы не можем реально использовать. Раньше память была очень дорогим ресурсом. Сегодня это уже не совсем так, но мы по-прежнему не хотим тратить ее впустую.

Фрагментация памяти это очень большая тема и мы посмотрим на нее только с точки зрения виртуальной памяти. Когда вы выделяете память из виртуальной памяти, проблемы с фрагментацией не будет.

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

Физическая память не фрагментируется при выделении виртуальной памяти.Физическая память не фрагментируется при выделении виртуальной памяти.

Здесь мы сначала выделяем красные страницы и освобождаем некоторые из них, оставляя дыры в адресном пространстве и физической памяти. Однако это не мешает нам выделить адресное пространство под фиолетовые страницы. Каждая фиолетовая страница может быть отображена на одну из страниц-дырок, которые образовались ранее, без необходимости выделения дополнительной физической памяти.

Обратите внимание, что в адресном пространстве у нас все еще остается фрагментация. Т.е. мы не можем выделить большой непрерывный блок памяти в адресном пространстве, где находятся красные страницы. Фрагментация адресного пространства, на самом деле, нас особо не беспокоит, потому что, как было сказано выше, обычно адресное пространство на 99.999999988% пустое. Так что у нас нет проблем с поиском смежных страниц в адресном пространстве. (Но в 32-битных системах это совсем другая история.)

Недостаток такого подхода по сравнению с обычным аллокатором заключается в том, что нам приходится округлять выделяемую память по размеру страницы, которая в современных системах обычно составляет 4 КБ. Это означает, что мы не используем всю доступную память проблема, которая называется внутренней фрагментацией.

Есть несколько способов решения этой проблемы. Для объектов с неизменяемым размером можно использовать пул объектов выделить страницу памяти и разместить там столько объектов, сколько поместится.

Размер динамически увеличивающегося буфера можно сделать соответствующим размеру страницы. Это простой, но интересный метод, о котором я очень редко слышу. Допустим, у вас есть массив объектов размером 300 байт. Обычно при необходимости размещения большего количества записей вы увеличиваете размер массива геометрически, например, удваивая. Таким образом, получается увеличение количества элементов с 16 до 32 до 64 и до 128 элементов. Геометрический рост важен, чтобы было меньше затрат на частое увеличение массива.

Однако 16 * 300 = 4800. При выделении виртуальной памяти вам придется округлить это до 8 КБ, тратя впустую почти целую страницу. Но это можно легко исправить. Вместо того чтобы концентрироваться на количестве элементов, мы просто увеличиваем размер буфера кратно размеру страницы: 4 КБ, 8 КБ, 16 КБ, 32 КБ, , а затем помещаем туда столько элементов, сколько поместится в него (13, 27, 54, 109,). Это по-прежнему геометрический рост, но теперь внутренняя фрагментация составляет в среднем всего 150 байт вместо 2 КБ.

Мне кажется странным то, что стандартные аллокаторы не используют преимуществ виртуальной памяти для борьбы с фрагментацией. Большинство аллокаторов, которые я видел, получают большие участки памяти из ОС, вместо того, чтобы работать со страницами виртуальной памяти.

Может получать от ОС большие участки памяти эффективнее? Здесь мои знания довольно поверхностны. Но я не думаю, что это так. Возможно, использование больших страниц будет более производительным, потому что будет меньше таблица страниц и эффективнее будет использоваться кэш TLB. Но, учитывая фиксированный размер страницы, я не думаю, что это имеет значение один большой кусок виртуальной памяти у вас или много маленьких, потому что разрешение адресов в любом случае выполняется страница-к-странице. И даже если вы выделяете большие непрерывные фрагменты памяти, в физической памяти они все-равно часто не будут непрерывными.

Возможно, появятся некоторые дополнительные затраты памяти ОС для отслеживания большого количества отдельных выделений памяти. Также время тратится на системные вызовы выделения и освобождения страниц. Может быть, в этом и есть причина. Или просто дело в том, что аллокаторы написаны для работы в различных средах и в 32-битных системах и в системах с большими страницами поэтому они не могут использовать преимуществ 64-битных систем и 4KБ страниц.

Кольцевой буфер

Об этом трюке я узнал из блога Фабиана Гизена (Fabian Giesen). Но, кажется, что это довольно давняя идея.

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

Кольцевой буфер хранит данные в массиве фиксированного размера. Когда массив заполняется, запись в него начинается с начала массива.

Кроме массива нам нужны еще указатели на "читателя" и "писателя" , чтобы знать, в какое место в буфере данные пишутся, а где читаются. Для этого мне нравится использовать uint64t, указывая общее количество записанных и прочитанных данных, что-то вроде этого:

enum {BUFFER_SIZE = 8*1024};struct ring_buffer_t {    uint8_t data[BUFFER_SIZE];    uint64_t read;    uint64_t written;};

Обратите внимание, что поскольку буфер начинает записываться сначала, мы не можем позволить указателю записи находиться слишком далеко от указателя чтения, иначе он начнет удалять данные, которые еще не прочитаны. По сути, BUFFER_SIZE управляет тем, как далеко вперед может уйти указатель на запись. Если буфер заполнен, то указатель на запись должен остановиться и дождаться чтения. Если буфер пустой, то указатель на чтение должен остановиться и ждать записи данных.

Что неудобно в кольцевом буфере, так это то, что вам нужно специально обрабатывать переход в начало буфера. Если бы не это, то для записи в буфер можно использовать простой memcpy, но приходится обрабатывать достижение конца массива.

void write(ring_buffer_t *rb, uint8_t *p, uint64_t n){    uint64_t offset = rb->written % BUFFER_SIZE;    uint64_t space = BUFFER_SIZE - offset;    uint64_t first_write = n < space ? n : space;    memcpy(rb->data + offset, p, first_write);    memcpy(rb->data, p + first_write, n - first_write);    rb->written += n;}

Как бы это ни раздражало, но с чтением все еще хуже. Если бы не перезапись с начала, то для чтения вообще бы не потребовалось никакого копирования мы могли просто использовать данные непосредственно из буфера. Но с перезаписью нам понадобятся два вызова memcpy() для перемещения данных в непрерывный блок памяти для дальнейшей обработки.

Как здесь может помочь виртуальная память? Мы можем использовать технику "огромного массива" и просто зарезервировать большой массив вместо кольцевого буфера и фиксировать (commit) страницы по мере продвижения указателя на запись, а по мере продвижения читателя отменять фиксацию (decommit). При этом нам даже не нужно будет задавать фиксированный размер массива он просто может использовать столько памяти, сколько потребуется. Довольно красивое решение. Но учтите, что вам может понадобиться очень большой массив. Для буферизации сетевого потока 1 Гбит/с с аптаймом в течение года вам потребуется зарезервировать 4 ПБ (петабайта) памяти. К сожалению, как мы видели выше, 64-разрядная Windows ограничивает объем виртуальной памяти 256 ТБ. Кроме того, вызовы commit и decommit не бесплатны.

Но мы можем поступить и другим способом, воспользовавшись тем, что в одну физическую страницу может отображаться несколько виртуальных. Обычно это используется для совместного использования памяти разными процессами. Но можно использовать и в рамках одного процесса. Чтобы использовать этот подход для кольцевого буфера, создадим несколько страниц сразу после кольцевого буфера (ring buffer), указывающих на одну и ту же физическую память.

Кольцевой буфер (ring buffer) с маппингом страниц.Кольцевой буфер (ring buffer) с маппингом страниц.

Как видите, при таком подходе о "перезаписи с начала" за нас заботится система виртуальной памяти. В адресном пространстве мы всегда можем найти непрерывную копию памяти для кольцевого буфера, даже в физической памяти не будет непрерывных участков. Функции чтения и записи становятся простыми:

void write(ring_buffer_t *rb, uint8_t *p, uint64_t n){    memcpy(rb->data + (rb->written % BUFFER_SIZE), p, n);    rb->written += n;}uint8_t *read(ring_buffer_t *rb, uint64_t n){    uint8_t *p = rb->data + (rb->read % BUFFER_SIZE);    rb->read += n;    return p;}

Это намного лучше, но мы по-прежнему используем тот же объем физической памяти.

Обратите внимание, что настройка такой схемы размещения в памяти может быть немного запутанной. В Windows нужно создать отображение файлов в виртуальную память с помощью CreateFileMapping(). Да, даже если никакие файлы на диске не задействованы, все равно нужно использовать "отображение файла", потому что совместно виртуальная память используется именно так. Но поскольку файл на диске нам не нужен, то для дескриптора файла используется INVALID_HANDLE_VALUE, создающий отображение в файл подкачки. Затем мы используем MapViewOfFileEx(), чтобы настроить отображение на две области памяти. К сожалению, нет никакого способа гарантировать, что переданные области памяти будут доступны. Мы можем зарезервировать их, а затем освободить непосредственно перед вызовом MapViewOfFileEx(), но все равно остается промежуток времени, когда, если нам очень не повезет, кто-то другой может прийти и выделить что-то в этом пространстве адресов. Возможно, нам придется повторить попытку отображения несколько раз, прежде чем оно будет успешным. Но после этого мы можем использовать буфер, не беспокоясь ни о чем.

Если вы знаете какие-нибудь изящные трюки с виртуальной памятью, не упомянутые здесь, пишите мне в твиттере в @niklasfrykholm.

Дополнения про Linux

Выше я написал, что "Linux допускает overcommit (чрезмерное выделение памяти)". Но, как я недавно обнаружил, на самом деле это не совсем так, или, по крайней мере, это очень сильное упрощение.

По умолчанию Linux допускает "некоторый" избыточный commit (определяется эвристически). Потому что если вы отключите overcommit, то будете тратить много памяти зря, поскольку процессы выделяют фактически не используемую память. С другой стороны, если вы разрешите слишком большой overcommit, вы можете столкнуться с ситуацией, когда процесс успешно выделил память, но при попытке получить к ней доступ, он не сможет этого сделать, потому что у системы не будет физической памяти. Для предотвращения таких ситуаций приходит OOM killer и убивает некоторые процессы.

Вы можете настроить систему, чтобы разрешить неограниченный overcommit (vm.overcommit_memory = 1) или указать ограничение (vm.overcommit_memory = 2). См. https://www.kernel.org/doc/Documentation/vm/overcommit-accounting

Но как разработчик вы не можете рассчитывать на то, что этот параметр будет установлен на определенное значение на машине пользователя. Вы должны убедиться, что работа вашей программы не зависит от этого параметра.

Это можно реализовать так же, как в Windows: разделить операции резервирования (reserve) и подтверждения (commit). Резервирование памяти не зависит от параметра overcommit_memory.

По документации mmap() это не совсем очевидно, но виртуальную память в Linux можно зарезервировать через вызов mmap() с PROT_NONE. После этого commit зарезервированной памяти можно сделать, используя системный вызов mprotect().

Примечание Использование MAP_NORESERVE вместо PROT_NONE не работает, когда overcommit_memory = 2, поскольку в этом случае флаг MAP_NORESERVE игнорируется. См. https://lwn.net/Articles/627557/


Перевод статьи подготовлен специально для будущих студентов курса "Программист С".

Также приглашаем всех желающих зарегистрироваться на открытый онлайн-вебинар: "ООП на C: пишем видеоплеер".

Подробнее..

Храним числа экономно

20.07.2020 00:13:49 | Автор: admin

Недавно в одном из проектов встала задача: есть набор множеств (Set), которые надо достаточно эффективно хранить в оперативной памяти. Потому что множеств много, а памяти мало. И с этим надо что-то делать.

Так как язык, на котором всё это написано C#, то есть нюансы. А именно, что стандартный HashSet<int> на хранение одного числа тратит 16 байт, также влияет филл фактор. Есть более эффективные реализации (когда-нибудь и про них напишу), но с другой стороны, можно же тупо хранить в массивах, по 4 байта на число (требуется хранить инты), что достаточно эффективно. Но можно ли уменьшить ещё?

Сразу скажу, у меня нет ответа, как лучше сделать, возможно его не существует, ибо есть множество факторов, связанных с особенностями распределения конкретных данных. Но есть идеи, которыми я поделюсь: какие варианты экономии памяти существуют. Также рекомендую до прочтения поста подумать самостоятельно, всё-таки это неплохая разминка для ума. Для определённости сформулирую задачу следующим образом:

Есть набор неотрицательных уникальных интов (32 бита). Требуется хранить их эффективно в оперативной памяти, из операций создание набора и получение всех элементов. Не нужно получать элементы по индексу, добавлять новые или удалять.

В статье будет много букв и цифр и ни одной картинки (кроме упакованного котика на КДПВ).


Я специально не указываю что за проект, что за задача конкретно, т.к. в целом, это неважно. Допустимые решения сильно зависят от данных. Какие-то лучше подходят для одних, какие-то для других, также не забываем про скорость работы. Где-то лучше максимально экономить память, а где-то стоит соблюдать баланс.
Также, не рассматриваю решения вида тупо хранить на диске и использовать кеш для горячих данных, это отдельная задача.
Просто для понимания количества данных, с которыми я столкнулся: несколько миллионов сетов, в каждом из которых от одного элемента до двух миллионов. В памяти это занимает около 10ГБ


Итак, у нас есть базовые данные массив из интов, 4 байта (32 бита) на число. Будем отталкиваться от этого показателя.
Для начала выскажу гениальную мысль: чтобы число занимало в памяти меньше 32 бит, надо хранить его, используя меньшее количество бит. Крутая идея, да? А люди за подобное получают известность и признание. Так что чем я хуже.

Лирическое отступление: несколько лет назад специалисты из РЖД выяснили, что если делать колёса круглыми и одинакового размера, то поезд идёт быстрее и тише.


Разделяем числа по размеру


Для начала простое решение: Числа от 0 до 255 можно хранить с помощью 1 байта на число, до 65536 двумя, до 16777216 тремя. Отсюда первое решение:
Создаем 4 массива, в одном храним числа по 1 байту, в другом по 2, в третьем по 3, а что в четвёртом, предлагаю догадаться самостоятельно.
Хлоп, и уже мы экономим. Но зачем оставаться на достигнутом? Давайте будем использовать 32 массива! И хранить числа по 1, 2 бита. Стало ещё экономнее.

С другой стороны, что есть массив? Это указатель на блок памяти (8 байт), длина и для C# ещё память на сам объект массива (20 байт). Итого, каждый массив нам обходится в 32 байта (на самом деле, в C# объект занимает минимум 24 байта с шагом по 8, из которых 20 байт на объект, а 4 на то что осталось или тупо на выравнивание). Здесь и далее расчёты для 64-х битной системы. Для 32 бит указатели в 2 раза меньше, выравнивание тоже на 4, так что почти всё экономнее в 2 раза.

К чему этот пассаж? К тому, что 32 массива сожрут у нас 1КБ памяти просто на самих себя. Что с этим делать? А всё просто: будем хранить эти 32 массива в одном массиве!
В первом элементе храним длину однобитного массива, потом сам массив, потом длина для двух бит и т.д. В результате, всего 32 байта накладных расходов и эффективное хранение.

Пытливый читатель (всегда нравилась эта фраза) может заметить некоторую проблему: для хранения чисел из одного бита мы вначале потратим 2 бита на длину (0, 1 или 2), а потом 2 бита на сами числа. А ведь можно потратить всего 2 бита: первый бит есть ли 0, второй есть ли 1.

Мы только что придумали битовую карту. Можно сильно не париться и хранить числа от 0 до 255 этим методом есть число 1, нет 0. И потратить на это 32 байта (8 бит в байте * 32 = 256). Естественно, с каждым новым значением эффективность карты начинает падать. Т.е. для хранения всех интов нам нужно 536870912 байт Как-то многовато. Так что, когда остановиться: на 256-ти, на 16-ти, на 65536-ти зависит от данных. Пусть будет 256. Мне нравится это число, красивое.

Т.е. первые 256 чисел храним битовой картой, дальше храним длину чисел определённой длины в битах и сами числа.

Но смотрите, что получается: числа от 0 до 511 требуют для хранения 9 бит. В тоже время, мы числа от 0 до 255 мы уже сохранили. Т.е. в диапазоне 9 бит не может попасться число 12. Только 256 и больше. Так зачем их ранить 9 битами, если можно хранить число от 0 до 255 и потом прибавить в уме недостающее 256. Сэкономили ещё один бит! Естественно каждый следующий диапазон тоже будет экономнее на 1 бит. Мы молодцы!

Что ещё можно сделать? А можно посмотреть на данные. Если они очень плотные (1,2,3,5,6), то можно хранить не сами числа, а те, которых нет (4). Т.е. вместо хранения условных 5 чисел, будем хранить одно. Простое правило: больше половины есть храним те, которых нет, иначе наоборот. Где хранить? А в длине! Смотрите: чтобы хранить числа длиной в 10 бит, нам надо 11 бит (потому что от 0 до 1024 включительно). Но при этом значений в 11 бит можно засунуть 2048, а используем мы только 1025. Вот и будем хранить: положительная длина храним числа. Отрицательная храним то, чего нет. Детальный расчёт предлагаю совершить читателю самому в качестве самостоятельного упражнения (потому что я не уверен, что всё сойдётся, так что сделаю вид, что так и надо).

В результате мы получили: массив, в котором первые 16 байт битовая маска наличия чисел от 0 до 255, дальше длина с указанием храним числа или их отсутствие, сами числа, битовая длина для следующего и т.д.

После того, как вы это реализуете, да ещё и без ошибок, думаю, вы отправитесь прямиком в дурку, последующие программисты, пытающиеся понять этот код отправятся за вами следом. Так что давайте попробуем ещё варианты.

Думаем над порядком


Смотрите. У нас есть массив. Что у него есть, в отличие от множества? А есть у него: порядок элементов. Это дополнительная информация, а мы её ещё никак не заиспользовали. Что же можно с этим сделать?
А можно хранить не сами элементы, а разницу между ними:
1,2,3,4,8 => 1,1,1,1,4
Т.е. первый храним как есть, второй добавляем значение первого ко второму и т.д. Что нам это даёт? А то, что если мы заранее отсортируем массив, то у нас значения в нём станут в целом меньше, и их можно хранить меньшим количеством бит.

Кроме того, у нас по условию задачи все элементы разные, т.е. мы от разницы можем ещё вычесть единичку, чтобы сэкономить битики:
1,2,3,4,8 => 1,1,1,1,4 => 1,0,0,0,3
Это несложно, так что почему бы и нет.

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

Храним длину числа битах перед самим числом
Неплохой вариант. Число занимает от 1 до 32 бит, т.е. на длину нам надо 5 бит, а потом само число. Можно для удобства отсекать крайние случаи (ну чо мы там наэкономим? копейки!), или наоборот, выделять их особо например, если длина 0 то значит число 0, если длина 1 число 1, если длина 2 то следующие 2 бита число 2,3,4,5 (мы уже знаем, что можем сдвигать на то, чего не может быть) и т.д.

А может хранить длину числа в самом числе?

Variable-length quantity
Как бы не мы первые задаёмся этим вопросом, поэтому есть стандартное решение. Используется для хранения строк в UTF-8 и много где ещё. Смысл простой:
Если число от 0 до 127 включительно храним его 1 байтом (хотя использовали только 7 бит). Если больше, то ставим 8-ой бит в 1 и используем следующий байт аналогичным образом (7 бит, не хватает флажок и следующий). Т.е. маленькие числа будут храниться одним байтом, чуть больше двумя, и так до 5.
Вы можете сказать фуу мы только что с битами игрались, а тут байты пошли, не круто! Да, не круто, с другой стороны, работать с байтами всё-таки проще чем с битами, чуть меньше экономия, зато выше скорость работы и понятнее код. Но тратить по биту в байте как-то не очень круто, может есть решения лучше?

Используем значения как флаги


Пропустим все рассуждения и сразу определимся. Будем хранить следующим образом:
  • числа от 0 до 253 будут храниться одним байтом. Если больше, то:
  • если число от 252 до 252+256=508 ставим значение 252, а в следующем байте число 252 (да-да, мы уже умеем сдвигать значения)
  • если от 252+256 до 252+256+65536, ставим 253 и используем следующие 2 байта для хранения самого числа ненужную разницу
  • если от 252+256+65536 до 252+256+65536+16777216, ставим 254 и 3 байта
  • иначе 255 и 4 байта.


Хорош ли этот способ? Всё относительно. В один байт мы можем запихать значения до 252, в то время как в VLQ только до 127, зато в 2 байта всего 508, а в VLQ уже 16383. Т.е. метод хорош, если у вас числа достаточно плотно расположены, и тут мы будем выигрывать. Но зато метод хорош тем, что его можно подгонять под разные диапазоны. Например, если мы знаем, что большинство чисел от 10000 до 50000, то мы можем хранить их всегда двумя байтами, но если вылезет какое-то большое число, мы напишем 65535 и будем использовать уже 4. Фактически, оптимизируем хранения нужного диапазона ценой неэффективного хранения ненужного.

Заключение


Мы рассмотрели основные способы экономить память (на самом деле, у меня иссякла фантазия, но признаваться в этом не буду). Данные техники можно комбинировать, использовать для других задач, дорабатывать под ситуацию. Какая техника в итоге лучше? Всё зависит от ваших данных. Берите их и пробуйте. Благо не надо реализовывать всё полностью сразу. Можно достаточно просто написать код, который просто оценит длину. А после оценки уже реализовывать то, что вам приглянулось.
Не стоит забывать и про скорость всего этого дела: готовы ли вы тратить много времени на подготовку данных или на получение. Стоит ли затевать борьбу с битами, или ниже байтов опускаться не стоит. Достаточно ли оптимизировать частые ситуации, оставив редкие с неэффективной реализацией. Можно ли в зависимости от данных использовать разные способы хранения (например, до 8 байт тупо хранить в массиве, т.к. побочные расходы сожрут весь выигрыш, а из 1 байта вообще хранить в псевдомассиве из одного элемента, т.е. в самом числе).

Также пару слов про сжатие: тут оно будет не очень эффективным. Алгоритмам сжатия очень нравятся повторения, а тут их не очень много. Если взять условный Zip, который в состоит из LZ77+Huffman, навряд ли что-то полезное получится с помощью LZ77, но Huffman может попытаться сэкономить байты. Получается, Zip будет бесполезным наполовину. А вот скорость просадит очень и очень сильно.

Ещё совершенно не рассмотрены ситуации, когда мы знаем о том, что у нас множеств много и мы можем хранить их всех вместе, используя различные срезы. Тут я признаюсь не уверен, что это получится. Сходу я не придумал варианты. Зато понял, что будет сложно. Впрочем, у вас могут быть другие мнения.

Так что делитесь идеями в комментариях, может я пропустил какого-то очевидного слона, который позволит сэкономить ещё больше байт и получить такой результат, что домохозяйки из рекламы моющего средства (которого достаточно одной капли) будут нам всем завидовать!
Подробнее..

Из песочницы Что нового я узнал о компьютере, когда решил написать Chrome Dino на C

22.08.2020 14:05:15 | Автор: admin


Немного о проекте


Для знакомства с языком с я решил написать небольшое приложение chrome dino, которое является неудачным клоном всем знакомого динозаврика из хрома. Из-за отсутствия классов в си я решил изобрести свой велосипед: поля и методы класса поместил в структуру, конструктором стала функция, которая возвращает эту структуру. Внутренние поля и методы скрыты, указав перед ними static. (Про это есть несколько статей)

.

typedef struct Barrier {    int width, height;    int *picture;    int x0, y0;} Barrier;Barrier* new_Barrier() {  Barrier* barrier = NULL;  barrier = malloc(sizeof(Barrier));  return barrier;}

Для удобства работы с графикой изображения хранятся в виде матрицы со
значениями [0, 1, 2, 3], это решение подтолкнуло на написание этой
статьи.
0 прозрачный,
1 синий,
2 черный,
3 серый.




Компьютер не знает что такое массивы, а двумерные тем более


Машинные операции способны записывать и считывать одиночные данные из ячейки памяти, а вот про набор данных машина ничего не знает и, работать с ними она не умеет. Возможность работы с массивами приходится реализовывать программно.


Сохранить в памяти одномерный массив можно записав определенное количество данных в последовательные ячейки памяти, а дальше приходится прыгать с бубном, т.к. методов для работы с ним нет.


Для перебора ряда данных (одномерный массив) берется адрес первого элемента, а затем в цикле (с шагом = размер типа данных) осуществляется переход на следующий адрес.


int n = 10;int step = sizeof(Barrier);Barrier* barrier = malloc(step * n);for (int i = 0; i < n; i += step) {  *(barrier + i) = data;}

Реализовать поиск элемента в двумерном массиве становится сложнее, по причине того, что весь массив записывается в последовательные ячейки и поиск приходится осуществлять по строке, а не матрице. Для поиска элемента матрицы в строке можно по формуле:


$$display$$A[ i ][ j ] = i * w + j$$display$$



где A двумерный массив,
&nbspi индекс строки,
&nbspj индекс столбца,
&nbspw длинна вложенного массива A (ширина массива)

Еще сложнее найти элемент трехмерного массива, для его поиска необходимо воспользоваться формулой:


$$display$$B[ i ][ j ][ k ] = i * w * h + j * w + k$$display$$



где B трехмерная матрица,
&nbspk индекс ряда двумерных матриц,
&nbsph длина вложенного массива B(высота матрицы).

Понятно, что для реализации работы с большей вложенностью массивов необходим единый алгоритм поиска его элемента:


$$display$$C[a_1][a_2]...[a_n] = \sum_{i = 1}^n a_i * L_{i - 1} * ... * L_1$$display$$


где C n-мерный массив,
&nbspn вложенность,
&nbsp$inline$a_i$inline$ индекс i-го массива,
&nbsp$inline$L_i$inline$ длинна массива i.

Если за ось ординат принять количество операция компьютера, а за ось абсцисс вложенность, то можно увидеть, как растет количество операций для вычисления элемента массива с увеличением вложенности. (Сумма и умножение приняты за одну операцию).




Помнить о памяти


В высокоуровневых языках имеются сборщики мусора и выделение памяти работает под капотом языка. В низкоуровневых языках приходится это делать самостоятельно: перед тем как записать данные в память, нужно зарезервировать некоторую ее область. Для набора данных необходимо самостоятельно высчитывать количество памяти для резервации.


Рассмотрим случай одномерного массива c элементами типа Barrier. Если количество элементов известно заранее, то для такого массива память выделяется один раз. В случае динамического массива, приходится каждый раз пересчитывать размер выделяемой для него памяти (если длина массива изменяется). Тогда для реализации стандартного метода push (добавление элемента в конец массива) необходимо выделить область памяти (равный сумме размера старого массива и величины типа элемента) и записать туда новый массив, а старый удалить. То же и с удалением элемента из массива.


int n = 10;int step = sizeof(Barrier);Barrier* barrier = malloc(step * n);for (int i = 0; i < n; i += step) {    *(barrier + i) = data;}n = 11;free(barrier);barrier = malloc(step * n);for (int i = 0; i < n; i += step) {    *(barrier + i) = data;}

Можно сделать вывод: изменение размера массива довольно затруднительная операция, особенно если идет большой цикл добавления элементов в массив. Некоторые высокоуровневые языки выделяют чуть больше области памяти под массивы (например, ArrayList в java), видимо для повышения производительности.



Не примитивный примитив


В высокоуровневых языках присутствуют как типы данных, передающиеся по ссылке, так и данные передающиеся по значению. Но для передачи данных по значению необходимо иметь ссылку на переменную, т.е. примитивный тип не такой уж примитивный? В ассемблере любая переменная хранит как ссылку на ячейку памяти, так и значение, которое в ней хранится. Каждая переменная хранить адрес своей ячейки и значение (значением также может быть адрес другой ячейки). Но где же хранятся ссылки на адреса ячеек памяти? Оказывается, когда компилятор создает машинный код, он автоматически заменяет имена всех переменных их смещениями. Значит, каждая переменная может передаваться по ссылке, но в высокоуровневых языках эта возможность скрыта для разработчика.



Посмотреть проект можно туть.
Подробнее..

Ищем максимальную разницу между соседями. User-friendly-разбор задачи по алгоритмам

08.12.2020 12:05:45 | Автор: admin
Привет, Хабр!

Давайте поговорим про алгоритмы. Новички часто воспринимают их как что-то тяжёлое, сложное и непонятное, и отчасти это правда, но алгоритмы это базис. А чем лучше вы знаете базис своей специальности, тем с большей вероятностью преуспеете в ней.



Сегодня мы посмотрим на одну красивую задачу по алгоритмам. Не будем отпугивать людей от работы с алгоритмами на самом старте, поэтому в нашем разборе не будет ни развесистых деревьев отрезков, ни разномастных оптимизаций задачи о рюкзаке, ни вероятностных тестов на простоту. User-friendly algos.

Вот задача: найти максимальную разницу между соседями.

Дан массив из N целых чисел. Он никак не упорядочен, а числа могут повторяться. Предположим, что мы отсортировали его и вычислили разницу между каждой парой последовательных элементов. Необходимо найти максимальную такую разницу и сделать это наиболее оптимальным способом.

Сложно? Можете попробовать сделать это до того, как нажмёте Читать дальше, а потом проверим решение.

Итак, поехали. Максимальная разница между соседями.

Рассмотрим пример:
Пусть дан массив из N=11 элементов.
A = [-1, -3, 10, 20, 21, 4, 3, 22, 10, -2, 15]

Cначала решим задачу наивно, это часто помогает. Мы можем сделать именно то, что от нас требует условие задачи отсортировать числа и найти разницу между соседними элементами. В зависимости от того, какую сортировку мы будем использовать, сложность решения будет варьироваться.

Если используем qsort или mergesort, то временная сложность составит O(N log N). Если нам известно, что числа распределены достаточно плотно на множестве целых чисел, то можно использовать сортировку подсчётом. Тогда мы получим O(U + N), где U разность между максимальным и минимальным элементом. Случай относительно редкий, но стоит помнить про такую возможность.

После сортировки получим массив:
As = [-3, -2, -1, 3, 4, 10, 10, 15, 20, 21, 22]
Выпишем массив разностей: D = [1, 1, 4, 1, 6, 0, 5, 5, 1, 1]
Получаем, что максимальная разница составляет 6.

Теперь подумаем, можно ли решить задачу быстрее? При переборе пар соседних элементов мы будем рассматривать много пар с маленькой разностью. Такие пары, возможно, и не смогут никогда дать наибольшую разность. И действительно, в отсортированном массиве у нас есть N-1 пара соседних чисел, разность между максимумом и минимумом пусть равна U. Тогда у наибольшей разности значение должно быть хотя бы U / (N 1). Эта оценка верна по принципу Дирихле.

Если голуби рассажены в клетки, причём число голубей больше числа клеток, то хотя бы в одной из клеток находится более одного голубя.


9 клеток содержат 10 голубей, по принципу Дирихле, хотя бы в одной клетке находятся более одного голубя (Википедия)

Пусть D[1] = As[2] As[1], D[n 1] = As[n] As[n 1], As[i] i-й элемент отсортированного массива. Тогда D[i] >= 0, D[1] + + D[N-1] = U.

Если предположить, что максимум из всех D[i] меньше U/(N-1), то вся сумма D[1] + + D[N-1] будет строго меньше U противоречие.

Отлично, мы получили нижнюю оценку на максимальную разность! Теперь попробуем как-то локализовать слишком близкие друг к другу элементы разобьём отрезок от минимального до максимального элемента на полуинтервалы длиной L=U/(N-1). Каждый элемент попадёт ровно в один полуинтервал. Получим разбиение всех элементов на непересекающиеся группы, их ещё называют батчами.

Определить, в какой именно из них попал элемент x, очень просто надо вычислить 1 + int((x a_min) / L) (нумеруем с единицы), где a_min минимальный элемент в массиве A, его можно найти за один проход по исходному массиву. Исключение составит только максимальный элемент элементы с таким значением лучше сделать отдельным батчом.

На рисунке представлено распределение из описанного выше примера. Для ясности проделаем эту процедуру руками:

U = 22 (-3) = 25, N = 11 => L = 25/(11-1) = 2.5
A = [-1, -3, 10, 20, 21, 4, 3, 22, 10, -2, 15]
(-1 (-3)) / 2.5 = 0.8 => batch = 1
(-3 (-3)) / 2.5 = 0 => batch = 1
(10 (-3)) / 2.5 = 13/2.5 = 5.2 =>batch = 6
(20 (-3)) / 2.5 = 23/2.5 = 9.2 => batch = 10
(21 (-3)) / 2.5 = 24/2.5 = 9.6 => batch = 10
(4 (-3)) / 2.5 = 7/2.5 = 2.8 => batch = 3
(3 (-3)) / 2.5 = 6/2.5 = 2.4 => batch = 3
(22 (-3)) / 2.5 = 10 => batch = 11
(10 (-3)) / 2.5 = 5.2 => batch = 6
(-2 (-3)) / 2.5 = 0.4 => batch = 1
(15 (-3)) / 2.5 = 7.2 => batch = 8



Распределение по батчам выполняется за линейное время и требует O(n) дополнительной памяти. Обратите внимание, что элементы из одного батча не могут дать максимальную разницу между двумя элементами. Мы специально подобрали его размер таким образом.

Где могут находиться два соседних по значениям элемента? Конечно же, в соседних непустых батчах! Например, на рисунке элементы из третьего и шестого батча могут идти подряд в отсортированном массиве, так как батчи между ними пустые. Понятно, что соседними будут только два элемента максимум из 3-го батча и минимум из 6-го. Аналогично, кандидатами на пару с максимальной разностью будут максимальный элемент первого батча и минимальный элемент третьего.

Выпишем все возможные пары элементов, которые могут дать наибольшую разность. Обозначим как min(i) минимальный элемент в i-й группе, как max(i) максимальный элемент.

max(1) = -1 min(3) = 3
max(3) = 4 min(6) = 10
max(6) = 10 min(8) = 15
max(8) = 15 min(10) = 20
max(10) = 21 min(11) = 22

Мы определили пары, которые стоит рассматривать. На практике необходимо сделать один проход по всем батчам, поддерживать последний непустой батч и максимальное значение в нём. Когда мы наткнёмся на следующий непустой батч, то найдём в нём минимум и попробуем обновить ответ.

Порадуемся мы решили задачу за время O(N).

На самом деле, мы использовали достаточно известную идею и по сути проделали первые шаги карманной сортировки, в оригинале её называют bucket-sort.


Элементы раскладываются по корзинам, а потом элементы в каждой корзине сортируются


В худшем случае она работает за O(n^2), но среднее время работы при достаточном количестве батчей и равномерном распределении элементов составляет O(n).

Но постойте, а как же случай, когда U=0, почему вы не рассмотрели его?, спросит внимательный читатель. Этот случай вырожденный, вот мы его и не рассмотрели, но давайте сделаем это сейчас для полноты вариантов.

Если разница между минимумом и максимумом равно нулю, то максимальная разница тоже равна нулю. Собственно, это всё.
Подробнее..

Как мы в IVI используем массивы в ClickHouse для подсчета продуктовых метрик

25.02.2021 14:18:30 | Автор: admin

IVI кросс-платформенный сервис, а значит, мы должны анализировать метрики всюду: на вебе, телевизорах и мобильных приложениях. Продукт непрерывно развивается, чтобы стать максимально эффективным, удобным и повысить ценность и привлекательность подписки. Перед тем, как внедрить какую-то новую фичу, мы проводим a/b-тесты и исследуем, на сколько востребованным окажется нововведение и как оно повлияет на конверсию или смотрение. Одновременно у нас может проверяться до 70-ти гипотез, от которых непосредственно зависят планы по развитию продукта.

Для того, чтобы правильно оценить успешность или неуспешность теста, требовалось технологичное решение. Тут рассказывали о том, как мы перешли на ClickHouse (а также о его проблемах на январь 2018). Новая схема ETL позволила нам иметь хранилище, толерантное к дубликатам. При ошибке в коде мы всегда можем откатить consumer offset в kafka и обработать часть данных снова, не прилагая лишних усилий для движения данных. Хотим рассказать о том, как мы в IVI используем ClickHouse, чтобы посчитать метрики для решения разных продуктовых задач и понять, что мы действительно делаем продукт лучше, а не придумываем фичи, которыми никто не будет пользоваться.

О массивах и махинациях с монетизацией контента.

Сперва введем ряд обозначений, которые будем использовать. На IVI есть несколько моделей монетизации. AVOD большой каталог бесплатных фильмов и сериалов, для просмотра которых придётся посмотреть рекламу. SVOD контент по подписке, расширенный каталог без рекламы. TVOD/EST контент, который доступен за отдельную плату и не входит в SVOD. EST покупка навсегда, TVOD аренда фильма, нужно начать просмотр в течение 30 дней, а закончить за 48 часов. Почему так дорого? У меня есть подписка, а я еще должен платить за отдельные фильмы? Ну совсем! Да этому фильму уже 20 лет, а я должен за него заплатить?! 600 рублей за аренду?! - подобное я слышу от друзей, таксистов, врачей по ДМС, преподавателей в университете и даже от родителей. Давайте разбираться.

Есть фильм, а есть правообладатель. Последний решает, в каком формате станут продавать контент. Заключается контракт, в котором описано, по какой модели будет доступен фильм, и если в контракте указано Доступна только TVOD-модель (как было, например, для онлайн-премьеры Человека-невидимки или Эммы), то условия должны быть выполнены. Но времена меняются, контракты перезаключаются, а контент, который был доступен только по модели TVOD/EST, может перетечь в подписку (т. е. в SVOD). И естественно, нельзя не поделиться этой информацией с пользователями.

В результате изменения модели монетизации контента перед нами встает задача объяснить бизнесу, как влияет коммуникация о переходе контента из TVOD/EST в SVOD на выручку и отток. Любая коммуникация с пользователем это ресурсы: человеко-часы, деньги на смс и прочее. Соответственно, нужно убедиться в том, что эти затраты оправданы (ведь экономика должна быть экономной). Мы стараемся проводить большинство коммуникаций в виде a/b-тестирования. Во-первых, чтобы убедиться в их полезности, а во-вторых, чтобы понимать, какие работают, а какие нет.

Переформулируем задачу для себя: провести a/b-тест, связанный с коммуникацией о переходе контента в SVOD из TVOD/EST, чтобы оценить изменение метрик. Выберем для себя ряд показателей, которые будут ключевыми в принятии решения:

1) количество зашедших на карточку контента;

2) количество смотрящих;

3) количество оформивших подписку SVOD;

4) количество купивших TVOD/EST;

5) выручка SVOD;

6) выручка TVOD/EST;

7) конверсия в оформление подписки после захода на карточку контента;

8) конверсия в покупку TVOD/EST после захода на карточку контента.

Для нас важна последовательность действий пользователя из тестовой группы: увидел коммуникацию -> заинтересовался предложением -> оформил подписку (или посмотрел перечисленные тайтлы). Как правило, эта последовательность отличается от блуждания: зашел на ivi -> погулял по карточкам контента -> посмотрел бесплатно -> погулял по карточкам контента -> купил подписку (контент) -> посмотрел контент.

У нас есть инструмент, который позволяет группировать события в массивы по признакам и по флагам в сессии (подробнее о массивах в ClickHouse тут).

У каждого массива в БД своя функция, например, массив, в котором хранятся a/b-тесты, массив с url ресурса, массив с событиями и их индексами в сессии и т.д. Вот маленькая шпаргалка, то, что необходимо понять перед составлением сложных мозгодробильных запросов:

arrayElement( "Вытащить в массиве элемент номер

details.int_value, В массиве таком-то

indexOf( найти номер элемента в массиве

details.name, В массиве таком-то

id' элемента такого-то

)

) in (1,2)

Итак, возьмем запрос, с помощью которого мы считали метрики для данной задачи, и посмотрим на него внимательно. Идея следующая:

берем только необходимые события захода на карточку контента, просмотров и покупок;

джойним на покупки, чтобы посчитать выручку;

собираем в массивы с группировкой по пользователю и дате и с помощью функции arrayCumSum инкрементально размечаем события перехода на карточку контента;

разворачиваем массивы и снова уже дополнительно группируем по счетчику перехода на карточку контента для того, что получить цепочки, начинающиеся с захода на КК

создаем флаги наличия просмотра или покупки в рассматриваемых цепочках;

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

считаем события в необходимой агрегации.

Итого. Массивы и возможность взять узкий срез помогли нам корректно оценить результаты эксперимента. Кратко они звучат так: общайтесь с пользователями, им это нравится.

Когда массивы излишни

Давайте отдельно поговорим о кейсе, когда нет смысла использовать массивы.

На IVI есть классная фича вход по коду (см. видео). Если вы авторизованы через мобильное приложение, то все, что вам надо для авторизации на ТВ ввести код с телефона в приложении IVI в своём Smart TV. Для пользователей, у которых нет чуда техники magic mouse, это по-настоящему полезная штука.

Вход по кодуВход по коду

Если мы хотим понять, сколько человек активно пользуется входом по коду, массивы нам не нужны, достаточно просто сделать count() по событиям. Джойны ClickHouse даются нелегко, как и некоторые сабселекты. Но в ряде кейсов сложные конструкции и не требуются, достаточно простого решения, ведь просто не значит неправильно.

Задача: оценить, как часто люди используют флоу входа по коду на Smart TV. Это нужно, чтобы понять, достаточно ли мы уведомляем людей о новых фичах. Ведь важно не только иметь классный функционал, но и понимать, сколько человек о нём знают и пользуются.

Так выглядит стандартная схема авторизации/регистрации на Smart TV:

Нужно проанализировать воронку:

  1. количество пользователей, использующих Вход по коду ко всем авторизовавшимся;

  2. количество пользователей, авторизованных по почте ко всем авторизовавшимся;

  3. количество пользователей, авторизованных по телефону ко всем авторизовавшимся.

Так мы оценим, какой % людей использует функцию входа по коду. Делаем поправку на то, что в данном случае мы оцениваем только кросс-платформенных пользователей, которые проявляют активность и на Smart TV, и на телефоне.

Использование массивов для решения задачи авторизации/регистрации пустая трата времени. Достаточно проследить за тем, сколько людей и на каком шаге отваливаются.

Резюме. ClickHouse отличный инструмент, который при правильном использовании решает как сложные, так и простые задачи. Он позволяет оценить результаты вносимых изменений. Чтобы улучшить свой продукт, вам недостаточно делать дорогие фичи, нужно понимать, насколько они оправданы, а без аналитики это невозможно.

Пару слов о проблеме выбора.

Если вы дочитали до этого места, то вот ещё кое-что интересное.

Как лучше показывать акционные предложения на телевизоре? Не стоит множить кнопки на экране, ставя перед пользователем проблему выбора. Мы решили провести небольшой эксперимент, в рамках которого запустили продуктовую коммуникацию, разработав два дизайна одного и того же предложения. На варианте 1 есть только одна кликабельная кнопка, ДА (рис. 1). На варианте 2 кнопок две ДА и Не сегодня. Кроме того, в каждом варианте есть аппаратный back и крестик в правом верхнем углу, их тоже учитываем. Сделав обычный select from посчитали CTR (количество кликов на кнопку/количество показов экрана) и поняли, что лучшее, что есть в выборе его отсутствие. Вариант 1 оказался заметно продуктивнее.

P.S. Благодаря эксперименту мы также узнали о том, что крестик носит скорее эстетический характер, а большая часть пользователей предпочитает аппаратный back: в среднем 7 из 10 человек нажимают на back вместо того, чтобы навести magic mouse на Х.

Рис.1

Рис.2

Подробнее..

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru