Самая дешевая структура для деференции?

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

Пример использования API: MyStruct * valuePtr = get(1234); и put(6789, &myStructInstance); ...базовый.

Я хочу свести к минимуму промахи кеша, поскольку я быстро и случайным образом читаю записи из этого массива, поэтому я предварительно malloc(sizeof(MyType) * MAX_ENTRIES) гарантирую локальность ссылок, насколько это возможно.

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

Как мне реализовать свой ассоциативный массив для повышения производительности? Мысли до сих пор...

  • Должен ли я передать ассоциативному массиву один указатель void * на массив значений malloced и разрешить ему использовать его внутри (для чего нам нужно будет гарантировать соответствующий размер массива ключей)? Могу ли я сделать это в общем случае, поскольку тип должен (?) быть известен для индексации в массиве значений?
  • Есть ли у меня отдельный void * valuePtrs[] в ассоциативном массиве, чтобы эти указатели указывали на каждый элемент в массиве значений malloced? Казалось бы, чтобы избежать необходимости знать о конкретном типе?
  • Должен ли я использовать псевдогенерики C и, таким образом, разрешить get() возвращать определенный тип значения? Конечно, в этом случае единственным преимуществом является отсутствие необходимости явного приведения, например. MyStruct* value = (MyStruct*) get(...)... элемент массива все еще должен быть разыменован, и поэтому он имеет те же накладные расходы?

И вообще, имеет ли смысл описанный выше подход к минимизации промахов?


c collections performance data-structures memory-layout
person Engineer    schedule 10.02.2015    source источник
comment
Пожалуйста, рассмотрите возможность показать, как вы представляете API для использования массива, это поможет сделать его более конкретным.   -  person unwind    schedule 10.02.2015
comment
@unwind Как вы и просили, см. второй абзац.   -  person Engineer    schedule 10.02.2015
comment
Да... И для этих строковых примеров вы предполагаете, что хранимые данные внутри массива будут просто указателем на строку, а не самой строкой? Если это просто указатель, то, конечно, вы будете использовать void *, поскольку он может указывать на что угодно, и тогда ваш массив становится массивом указателей.   -  person unwind    schedule 10.02.2015
comment
@unwind На самом деле хороший момент, позвольте мне адаптировать это, поскольку строки - плохой пример. В большинстве случаев массив значений будет массивом структур. РЕДАКТИРОВАТЬ: обновлено соответственно.   -  person Engineer    schedule 10.02.2015
comment
Да, строки — плохой пример для подобных вещей. Теперь, без дженериков, я не понимаю, как вы можете иметь функцию, возвращаемый тип которой является динамическим, как вы показываете. Это должно быть bool get(void *value, const void *key) или что-то в этом роде, чтобы скопировать значение, размер которого неизвестен во время компиляции.   -  person unwind    schedule 10.02.2015
comment
@unwind, да, идиотизм с моей стороны: НЕ массив значений. Использование API обновлено. Дело в том, что это разыменование указателя должно быть достаточно дешевым, если локальность ссылки хорошая. Поэтому я готов использовать deref, а не обращаться к значениям напрямую. Возможно, это позволит вам дать более полный ответ.   -  person Engineer    schedule 10.02.2015

Ответы (2)


arrow_upward
1
arrow_downward

В обоих случаях производительность практически одинакова. В первом случае (реализация void*) вам нужно будет найти значение + разыменовать указатель. Итак, это две инструкции.
В другой реализации вам нужно будет умножить индекс на размер значений. Таким образом, эта реализация также запрашивает две инструкции. Однако первая реализация будет проще и понятнее. Кроме того, массив полностью прозрачен; пользователю не нужно знать, какие структуры находятся в массиве.

person Ruben Van Dijck    schedule 10.02.2015
comment
Спасибо Рубен. Фактически, поиск в ассоциативном массиве уже настолько эффективен, насколько это возможно для моего варианта использования, где время доступа для чтения в наихудшем случае важнее всего остального... Я выбрал поиск по бинарному поиску. Поэтому я боюсь, что этот ответ не очень полезен в его нынешнем виде. Если бы вы могли подробнее рассказать о void * добавлении еще одного разыменования, я могу по крайней мере +1 вам. - person Engineer; 10.02.2015
comment
Либо вы используете массив void*, имеющий полностью универсальный массив значений. Если вы хотите иметь значения, вам придется следовать указателю на его местоположение, таким образом добавляя инструкции. Также вариант (чтобы получить полуобщий массив значений) состоит в том, чтобы сделать его структурой, которая содержит массив значений (со значениями, а не указателем на значения) и размер записей в этой таблице. Таким образом, вы можете вычислить положение ваших записей, не зная, какая структура находится в массиве. Первый вариант лучше. Извините, мой первый ответ был неправильным. - person Ruben Van Dijck; 10.02.2015
comment
Еще раз спасибо, Рубен, это полезный отзыв. +1. - person Engineer; 10.02.2015

arrow_upward
1
arrow_downward

См. решения, классифицированные ниже с точки зрения плюсов и минусов (спасибо Рубену за помощь в моем мышлении)... Я реализовал варианты 2 и 5 для своего варианта использования, который несколько обобщен; Я рекомендую вариант 4, если вам нужна очень специфическая одноразовая структура данных. Вариант 3 является наиболее гибким, хотя и тривиальным для кода, а также самым медленным. Вариант 4 самый быстрый. Вариант 5 немного медленный, но с гибкостью в отношении размера массива и простотой общего использования.

Ассоциативная структура массива указывает на массив типизированных указателей:

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

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

Структура ассоциативного массива содержит массив указателей void *:

достоинства: не требуется значение ошибки, не требуется общий библиотечный код

минусы дорогостоящее двойное отключение, явное приведение типов после get(), требуется размер массива во время компиляции, если VLA не используются

Структура ассоциативного массива указывает на массив из void * значений:

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

минусы дорогостоящее тройное отключение, явное приведение типов после get(), требуется вычисление смещения, которое требует явной передачи значения sizeof

Ассоциативная структура массива содержит массив типизированных значений:

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

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

Ассоциативная структура массива указывает на массив типизированных значений:

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

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

person Engineer    schedule 10.02.2015