Хранение "хвостиков"

[Igors]

Ну вот допустим я захотел хранить 0, 1, 2, 3, 4 флота напрямую (до 16 байт), а для большего числа эл-тов уже вектор.

А уже далее ничто не мешает сделать

Код:

struct S
{
    size_t size;
    union {
        float data1[4];
        float *data2 {nullptr};
    }
};

Да, и здесь это будет проще и лучше чем boost::variant или QVarLengthArray. Но все же возможен вариант с куда меньшим оверхедом

Код

C++ (Qt)
struct CData {
 size_t size;
 size_t index;  // индекс в др контейнере float
};

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

Наверное, boost::small_vector

Это тот же самый QVarLengthArray. Похоже нужен cached_node_allocator, но разобраться там не так уж просто...

[Авварон]

Код

C++ (Qt)
struct CData {
 size_t size;
 size_t index;  // индекс в др контейнере float
};

Ну это почти эквивалентно вектору с кастомным аллокатором, к-ый уже предлагали.

[Авварон]

Подумал ещё. Мой вариант занимает 2*8 байт + данные или 8 байт + данные, если данных мало.
Ваш вариант занимает 2*8 байт + данные.
Где ж тут "куда меньший оверхед"? Разве что на динамическую аллокацию, ну так это ж еще пул писать надо, фрагментацию учитывать.

[Igors]

Ну это почти эквивалентно вектору с кастомным аллокатором, к-ый уже предлагали.

Если Вы имеете ввиду пост #26 то неясно что там предлагалось - упоминалось о "пулах", и что с того?

Подумал ещё. Мой вариант занимает 2*8 байт + данные или 8 байт + данные, если данных мало.
Ваш вариант занимает 2*8 байт + данные.

Если float data1[4], то никак не меньше 16 да плюс счетчик. Да и вообще я могу отпихнуться unsigned int (вместо size_t) и иметь всегда 8

Где ж тут "куда меньший оверхед"? Разве что на динамическую аллокацию, ну так это ж еще пул писать надо, фрагментацию учитывать.

В этом все дело. Чем поддерживать указатель на float? new/delete лучше вектора но при малых данных оверхед приличный. Напр 5 флотов - сам блок уже 32 байта плюс "обвязки" для кучи. А вот если мы храним данные в отдельном контейнере - они занимают ровно sizeof

[Racheengel]

Я предлагал пулы в виде списка структур для 2, 3 и 4 флотов. При этом данные хранятся в отдельном контейнере, а объект имеет указатель на элемент пула. Убился объект - освободился элемент в пуле (но физически он остался в памяти). Добавился объект - нашли первый свободный элемент пула и связали с объектом. Нету свободных - добавили.
Заимплементировать такой пул несложно.

Для 1 флота пул юзать не имеет смылса, т.к. флот займет столько же, сколько и указатель. А для бОльшего кол-ва данных - std::vector пойдет.

[Igors]

Я предлагал пулы в виде списка структур для 2, 3 и 4 флотов. При этом данные хранятся в отдельном контейнере, а объект имеет указатель на элемент пула. Убился объект - освободился элемент в пуле (но физически он остался в памяти). Добавился объект - нашли первый свободный элемент пула и связали с объектом. Нету свободных - добавили.
Заимплементировать такой пул несложно.

Позвольте, но ведь это (позорный?) "велосипед"   Обдумывал в этом направлении, соображения:

- почему не для 5 тоже (или произвольного числа)?
- почему бОльшая дырка не может заполняться?
- в какой-то момент оказалось "почти все в дырках", как "освободиться"?
и.т.д

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

[Racheengel]

Количество данных, которое имеет смысл держать в пуле, зависит просто от размера указателя на элемент в пуле. Допустим, в 32-битном приложении флоат займет 32 бита, и поинтер на элемент - тоже 32 бита. Т.е. 1 флот можно хранить просто в структуре данных. От 2 до N флотов уже займут больше, чем 1 поинтер - значит, имеет смысл, наверное, "пулить" (но мы всегда будем терять 32 бита из-за поинтера, вопрос в том, какой будет оверхед у вектора флотов std::vector<float>).

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

Да, это по сути велосипед, наверно. Но я не знаю, что еще предложить

[Igors]

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

Я имел ввиду расклад "мульен "свободных" (дырок) и только 10 "занятых" - а память-то распределена для всех

Да, это по сути велосипед, наверно. Но я не знаю, что еще предложить

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

Да, и заметьте, как красноречиво молчание "бустовских эстетов" А ведь задача явно из базовых..

[Racheengel]

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

[Old]

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

К сожалению, не все это понимают и поэтому регулярно пытаются там найти решения на все случаи жизни.

[Авварон]

В этом все дело. Чем поддерживать указатель на float? new/delete лучше вектора но при малых данных оверхед приличный. Напр 5 флотов - сам блок уже 32 байта плюс "обвязки" для кучи. А вот если мы храним данные в отдельном контейнере - они занимают ровно sizeof

Шта? Типа float *data - это УЖАС оверхед, а size_t index - нет? Шта?
Еще раз, sizeof(T*) == sizeof(size_t). Делая индекс вы ни на чем не экономите.
В "другом контейнере" лежит 5 флотов (5*4) + size ( + index (.
В куче лежит 5 флотов (5*4) + size ( + указатель в кучу (.
У меня оверхед по памяти в исходном варианте потому что флоатов в структуре 4, ну так это дань скорости, сделайте 2 флоата (1 дабл) и не будет оверхеда. Гибкость же.
Ваш вариант только отличается тем, что (по сути) вместо malloc используется кастомный аллокатор на пуле, но это вообще отдельная тема, когда их стоит/не стоит применять.

[Old]

Если использовать пулы, то можно сэкономить на хранении размера данных, оставив только указатель.
Т.е. структура будет хранить только указатель на float.

Код

C++ (Qt)
struct Data {
 ....
 float *m_data;
};
 

Код

C++ (Qt)
Data data;
data.m_data = FloatAllocator::alloc( 1 );    // Быстро возвращается указатель на буфер в пуле однофлоатов (данные хранятся компактно)
data.m_data = FloatAllocator::alloc( 2 );    // Быстро возвращается указатель на буфер в пуле двуфлоатов (данные хранятся компактно)
data.m_data = FloatAllocator::alloc( 4 );    // Быстро возвращается указатель на буфер в пуле четырехфлоатов (данные хранятся компактно)
data.m_data = FloatAllocator::alloc( 10500 );    // Алоцируется буфер в куче для указанного количества
 
size_t size = FloatAllocator::size( data.m_data );    // Возвращает доступное количество флоатов
 
FloatAllocator::free( data.m_data );    // Для пула просто пометка что буфер освободился, для не преаллоцированых буферов - освобождение
 

[Igors]

Шта? Типа float *data - это УЖАС оверхед, а size_t index - нет? Шта?
Еще раз, sizeof(T*) == sizeof(size_t). Делая индекс вы ни на чем не экономите.
В "другом контейнере" лежит 5 флотов (5*4) + size ( + index (.
В куче лежит 5 флотов (5*4) + size ( + указатель в кучу (.
У меня оверхед по памяти в исходном варианте потому что флоатов в структуре 4, ну так это дань скорости, сделайте 2 флоата (1 дабл) и не будет оверхеда. Гибкость же.

Вот как раз не та же. 4 флота хороши напр для 3D модели, которая чаще всего - треугольники, реже квадранглы, а остальные случаи (1, 2 и > 4) редки. Но в общем случае известно лишь что число флотов ("хвостиков") может быть мало, скажем, меньше 10. Нацеливаясь на какой-то конкретный случай Вы заметно проигрываете в остальных. Да и с uniоn неприятная возня, нужны геттеры/сеттеры. Не проблема конечно, но код явно не украшает.

Ваш вариант только отличается тем, что (по сути) вместо malloc используется кастомный аллокатор на пуле, но это вообще отдельная тема, когда их стоит/не стоит применять.

При условии что CData могут интенсивно удаляться - точно стоит (иначе достаточно вектора). Вопрос где взять такой аллокатор. В букваре ж нема... или я ошибаюсь?  

[OFF]

Шта?

Возможно Вам это кажется остроумным, но читать/понимать трудновато  [/OFF]

[Old]

Вопрос где взять такой аллокатор. В букваре ж нема... или я ошибаюсь?  

Одним алокатором тут не обойтись.
Есть boost::object_pool, можно взять его или написать свой пул (я бы писал свой). И на пулах пишите свой менеджер памяти, я чуть выше написал его возможности.

Код

C++ (Qt)
template<typename T, size_t maxPrealloc>
class Allocator
{
public:
    T    *alloc( size_t n );
    void  free( T * );
    size_t  size( T * );
};
 

Буферы для количества элементов менее maxPrealloc будет браться из преалоцированных пулов, все остальные выделяться в куче.
Напомню, здесь еще и на размере данных в CData экономиться.

[Авварон]

При условии что CData могут интенсивно удаляться - точно стоит (иначе достаточно вектора). Вопрос где взять такой аллокатор. В букваре ж нема... или я ошибаюсь?  

В общем, как обычно, задача сформулирована через жопу. Сначала вы пишете, что вектор ест слишком много памяти. Мы это обсуждаем 5 страниц. Потом оказывается, что "много памяти" - это один (!) лишний указатель, а на самом деле нам важна не память, а скорость аллокации. Собственно, см. мой эмоциональный пост.