Если, скажем, 32-разрядное целое переполняется, вместо обновления int до long мы можем использовать некоторый 40-битный тип, если нам нужен диапазон только в пределах 2 40 так что мы сохраняем 24 (64-40) бит для каждого целого числа?
Если да, то как?
Мне приходится иметь дело с миллиардами, а пространство - большим ограничением.
Это, конечно, возможно, но обычно это бессмысленно (для любой программы, которая не использует миллиарды этих чисел):
#include <stdint.h> // don't want to rely on something like long long
struct bad_idea
{
uint64_t var : 40;
};
Здесь var действительно будет иметь ширину 40 бит за счет much менее эффективный генерируемый код (оказывается, что "много" очень сильно ошибочно - измеренные служебные данные всего 1-2%, см. тайминги ниже) и обычно безрезультатно. Если вам не понадобится еще одно 24-битное значение (или значение 8 и 16 бит), которое вы хотите упаковать в одну и ту же структуру, выравнивание потеряет все, что вы можете получить.
В любом случае, если у вас нет миллиардов, эффективная разница в потреблении памяти не будет заметна (но дополнительный код, необходимый для управления полем бит, будет заметным!).
Примечание:
Вопрос, тем временем, был обновлен, чтобы отразить, что действительно нужны миллиарды чисел, поэтому это может быть жизнеспособным делом, предполагается, что вы принимаете меры, чтобы не потерять выгоды из-за выравнивания и заполнения структуры, то есть либо путем хранения что-то еще в оставшихся 24 битах или путем хранения ваших 40-битных значений в структурах по 8 каждый или их кратность).
Стоит экономить три байта в миллиард раз, так как для этого потребуется значительно меньшее количество страниц памяти и, следовательно, вызывать меньшее количество промахов кеша и TLB и, прежде всего, сбоев страниц (ошибка одной страницы, утягающая десятки миллионов инструкций).
В то время как вышеприведенный фрагмент не использует оставшиеся 24 бита (он просто демонстрирует часть "использование 40 бит" ), необходимо будет сделать что-то похожее на следующее, чтобы действительно сделать подход полезным в смысле сохранения памяти - - предположил, что у вас действительно есть другие "полезные" данные для ввода отверстий:
struct using_gaps
{
uint64_t var : 40;
uint64_t useful_uint16 : 16;
uint64_t char_or_bool : 8;
};
Размер и выравнивание структуры будут равны 64-битовому целому числу, поэтому ничего не будет потрачено впустую, если вы сделаете, например. массив из миллиардов таких структур (даже без использования расширений, связанных с компилятором). Если у вас нет использования для 8-битного значения, вы также можете использовать 48-битное и 16-битное значение (дающее больший запас переполнения).
В качестве альтернативы вы могли бы, за счет удобства использования, поместить 8 40-битных значений в структуру (наименее общий кратный 40 и 64 равен 320 = 8 * 40). Конечно, тогда ваш код, который обращается к элементам в массиве структур, станет намного более сложным (хотя, вероятно, можно реализовать operator[], который восстанавливает функциональность линейного массива и скрывает сложность структуры).
Update:
Написал быстрый тестовый набор, чтобы увидеть, какие издержки могут иметь битполы (и перегрузка операторов с помощью битполя). Отправленный код (из-за длины) на gcc.godbolt.org, тестовый вывод с моего компьютера Win7-64:
Running test for array size = 1048576
what alloc seq(w) seq(r) rand(w) rand(r) free
-----------------------------------------------------------
uint32_t 0 2 1 35 35 1
uint64_t 0 3 3 35 35 1
bad40_t 0 5 3 35 35 1
packed40_t 0 7 4 48 49 1
Running test for array size = 16777216
what alloc seq(w) seq(r) rand(w) rand(r) free
-----------------------------------------------------------
uint32_t 0 38 14 560 555 8
uint64_t 0 81 22 565 554 17
bad40_t 0 85 25 565 561 16
packed40_t 0 151 75 765 774 16
Running test for array size = 134217728
what alloc seq(w) seq(r) rand(w) rand(r) free
-----------------------------------------------------------
uint32_t 0 312 100 4480 4441 65
uint64_t 0 648 172 4482 4490 130
bad40_t 0 682 193 4573 4492 130
packed40_t 0 1164 552 6181 6176 130
Что можно увидеть, так это то, что дополнительные накладные расходы битовых полей небрежны, но перегрузка оператора с использованием битового поля как удобная вещь довольно радикальна (примерно на 3 раза) при доступе к данным линейно с учетом кэширования. С другой стороны, при случайном доступе это едва ли имеет значение.
Эти тайминги предполагают, что просто использование 64-битных целых чисел было бы лучше, поскольку они по-прежнему быстрее, чем битполы (несмотря на то, что они касаются большего объема памяти), но, конечно, они не учитывают стоимость ошибок страниц с гораздо большими наборами данных. Это может выглядеть совсем по-другому, если у вас закончилась физическая RAM (я не тестировал это).
Вы можете довольно эффективно объединить целые числа 4 * 40 бит в 160-битную структуру следующим образом:
struct Val4 {
char hi[4];
unsigned int low[4];
}
long getLong( const Val4 &pack, int ix ) {
int hi= pack.hi[ix]; // preserve sign into 32 bit
return long( (((unsigned long)hi) << 32) + (unsigned long)pack.low[i]);
}
void setLong( Val4 &pack, int ix, long val ) {
pack.low[ix]= (unsigned)val;
pack.hi[ix]= (char)(val>>32);
}
Они снова могут быть использованы следующим образом:
Val4[SIZE] vals;
long getLong( int ix ) {
return getLong( vals[ix>>2], ix&0x3 )
}
void setLong( int ix, long val ) {
setLong( vals[ix>>2], ix&0x3, val )
}
Предположительно, у вас есть много таких номеров где-то (в ОЗУ, на диске, отправлять их по сети и т.д.), а затем брать их один за другим и выполнять некоторую обработку.
Один из подходов был бы кодировать их с помощью VLE. Из документации Google protobuf (лицензия CreativeCommons)
Варины - это метод сериализации целых чисел, использующий один или несколько байтов. Меньшие числа занимают меньшее количество байтов.
Каждый байт в varint, кроме последнего байта, имеет самый значительный бит (msb) - это указывает на то, что есть дополнительные байты. Нижние 7 бит каждого байта используются для хранения двух дополнений представление числа в группах по 7 бит, наименее значимое первой группы.
Итак, например, вот номер 1 - это один байт, поэтому msb не установлено:
0000 0001А вот 300 - это немного сложнее:
1010 1100 0000 0010Как вы узнаете, что это 300? Сначала вы бросаете msb из каждый байт, так как это просто для того, чтобы рассказать нам, достигли ли мы конец номера (как вы можете видеть, он устанавливается в первом байте, так как там более одного байта в varint)
Доводы
против
(Edit: Прежде всего - то, что вы хотите, возможно, и имеет смысл в некоторых случаях: мне приходилось делать подобные вещи, когда я пытался что-то сделать для задачи Netflix и имел только 1 ГБ памяти; вероятно, лучше использовать массив char для 40-разрядного хранилища, чтобы избежать любых проблем с выравниванием и необходимость испортить прагмы компоновки пакетов; в-третьих - этот дизайн предполагает, что вы в порядке с 64-разрядной арифметикой для промежуточных результатов, только для большого хранилища массивов вы будете использовать Int40, в-четвертых: я не получаю все предложения, что это плохая идея, просто прочитайте, что люди проходят, чтобы упаковать структуры данных сетки, и это выглядит как игра для детей сравнение).
То, что вы хотите, это структура, которая используется только для хранения данных в виде 40-битных int, но неявно преобразуется в int64_t для арифметики. Единственный трюк - это расширение знака от 40 до 64 бит вправо. Если вы в порядке с unsigned ints, код может быть еще проще. Это должно помочь вам начать работу.
#include <cstdint>
#include <iostream>
// Only intended for storage, automatically promotes to 64-bit for evaluation
struct Int40
{
Int40(int64_t x) { set(static_cast<uint64_t>(x)); } // implicit constructor
operator int64_t() const { return get(); } // implicit conversion to 64-bit
private:
void set(uint64_t x)
{
setb<0>(x); setb<1>(x); setb<2>(x); setb<3>(x); setb<4>(x);
};
int64_t get() const
{
return static_cast<int64_t>(getb<0>() | getb<1>() | getb<2>() | getb<3>() | getb<4>() | signx());
};
uint64_t signx() const
{
return (data[4] >> 7) * (uint64_t(((1 << 25) - 1)) << 39);
};
template <int idx> uint64_t getb() const
{
return static_cast<uint64_t>(data[idx]) << (8 * idx);
}
template <int idx> void setb(uint64_t x)
{
data[idx] = (x >> (8 * idx)) & 0xFF;
}
unsigned char data[5];
};
int main()
{
Int40 a = -1;
Int40 b = -2;
Int40 c = 1 << 16;
std::cout << "sizeof(Int40) = " << sizeof(Int40) << std::endl;
std::cout << a << "+" << b << "=" << (a+b) << std::endl;
std::cout << c << "*" << c << "=" << (c*c) << std::endl;
}
Вот ссылка, чтобы попробовать: http://rextester.com/QWKQU25252
Вы можете использовать структуру битового поля, но это не спасет вас от любой памяти:
struct my_struct
{
unsigned long long a : 40;
unsigned long long b : 24;
};
Вы можете сжать любое число из восьми таких 40-битных переменных в одну структуру:
struct bits_16_16_8
{
unsigned short x : 16;
unsigned short y : 16;
unsigned short z : 8;
};
struct bits_8_16_16
{
unsigned short x : 8;
unsigned short y : 16;
unsigned short z : 16;
};
struct my_struct
{
struct bits_16_16_8 a1;
struct bits_8_16_16 a2;
struct bits_16_16_8 a3;
struct bits_8_16_16 a4;
struct bits_16_16_8 a5;
struct bits_8_16_16 a6;
struct bits_16_16_8 a7;
struct bits_8_16_16 a8;
};
Это избавит вас от некоторой памяти (по сравнению с 8-разрядными стандартными 64-битными переменными), но вам придется разделить каждую операцию (и, в частности, арифметические) на каждую из этих переменных на несколько операций.
Таким образом, оптимизация памяти будет "продаваться" для производительности во время выполнения.
Как следует из комментариев, это довольно сложная задача.
Наверное, лишние хлопоты, если вы не хотите сохранить много ОЗУ - тогда это имеет смысл. (Сохранение ОЗУ будет суммой бит, сохраненной в миллионах значений long, хранящихся в ОЗУ)
Я бы рассмотрел использование массива из 5 байтов / char (5 * 8 бит = 40 бит). Затем вам нужно будет сдвинуть биты из вашего (переполненного значения int - следовательно, long) в массив байтов для их хранения.
Чтобы использовать значения, смещайте биты обратно в long, и вы можете использовать это значение.
Тогда ваша память и память для хранения значения будут 40 бит (5 байтов), НО вы должны рассмотреть выравнивание данных, если вы планируете использовать struct для хранения 5 байтов. Дайте мне знать, если вам нужна разработка этих изменений смещения битов и выравнивания данных.
Аналогично, вы можете использовать 64-битный long и скрыть другие значения (возможно, 3 символа) в оставшихся 24 битах, которые вы не хотите использовать. Опять же - использование сдвига битов для добавления и удаления 24-битных значений.
Я предполагаю, что
unsigned char hugearray[5*size+3]; // +3 avoids overfetch of last element
__int64 get_huge(unsigned index)
{
__int64 t;
t = *(__int64 *)(&hugearray[index*5]);
if (t & 0x0000008000000000LL)
t |= 0xffffff0000000000LL;
else
t &= 0x000000ffffffffffLL;
return t;
}
void set_huge(unsigned index, __int64 value)
{
unsigned char *p = &hugearray[index*5];
*(long *)p = value;
p[4] = (value >> 32);
}
Возможно, быстрее обработать get с двумя сменами.
__int64 get_huge(unsigned index)
{
return (((*(__int64 *)(&hugearray[index*5])) << 24) >> 24);
}
Другим вариантом, который может быть полезным, будет использование структуры:
typedef struct TRIPLE_40 {
uint32_t low[3];
uint8_t hi[3];
uint8_t padding;
};
Такая структура займет 16 байт и, если выровнять по 16 байт, будет полностью входить в одну строку кеша. При определении того, какая из частей используемой структуры может быть дороже, чем если бы структура содержала четыре элемента вместо трех, доступ к одной строке кеша может быть намного дешевле, чем доступ к двум. Если производительность важна, следует использовать некоторые эталонные тесты, поскольку некоторые машины могут выполнять операцию divmod-3 дешево и имеют высокую стоимость для выборки в кеш-строке, тогда как другие могут иметь более дешевый доступ к памяти и более дорогой divmod-3.
Если вам нужно иметь дело с миллиардами целых чисел, я бы попытался выполнить инкапсуляцию массивов из 40-битных чисел вместо одиночных 40-битных чисел. Таким образом, вы можете протестировать различные реализации массивов (например, реализацию, которая сжимает данные "на лету", или, возможно, такую, которая хранит менее используемые данные на диске.) Без изменения остальной части вашего кода.
Здесь пример реализации (http://rextester.com/SVITH57679):
class Int64Array
{
char* buffer;
public:
static const int BYTE_PER_ITEM = 5;
Int64Array(size_t s)
{
buffer=(char*)malloc(s*BYTE_PER_ITEM);
}
~Int64Array()
{
free(buffer);
}
class Item
{
char* dataPtr;
public:
Item(char* dataPtr) : dataPtr(dataPtr){}
inline operator int64_t()
{
int64_t value=0;
memcpy(&value, dataPtr, BYTE_PER_ITEM); // Assumes little endian byte order!
return value;
}
inline Item& operator = (int64_t value)
{
memcpy(dataPtr, &value, BYTE_PER_ITEM); // Assumes little endian byte order!
return *this;
}
};
inline Item operator[](size_t index)
{
return Item(buffer+index*BYTE_PER_ITEM);
}
};
Примечание. memcpy -конверсия от 40-битного до 64-битного - это в основном поведение undefined, поскольку оно предполагает litte-endianness. Однако он должен работать на x86-платформах.
Примечание 2: Очевидно, что это код с доказательством концепции, а не готовый к производству код. Чтобы использовать его в реальных проектах, вам нужно добавить (среди прочего):
Item имеет ссылочную семантику, а не семантику значений, что необычно для operator[]; Возможно, вы можете обойти это с помощью некоторых умных трюков преобразования типа С++.Все они должны быть понятны для программиста на С++, но они сделают код примера намного дольше, не делая его более ясным, поэтому я решил опустить их.
В случае хранения нескольких миллиардов 40-битных целых чисел и принятия 8-битных байтов вы можете упаковать 8 40-битных целых чисел со знаком в struct (в приведенном ниже коде с использованием массива байтов для этого), и, поскольку эта структура обычно выровнена, вы можете создать логический массив таких упакованных групп и обеспечить обычную последовательную индексацию этого:
#include <limits.h> // CHAR_BIT
#include <stdint.h> // int64_t
#include <stdlib.h> // div, div_t, ptrdiff_t
#include <vector> // std::vector
#define STATIC_ASSERT( e ) static_assert( e, #e )
namespace cppx {
using Byte = unsigned char;
using Index = ptrdiff_t;
using Size = Index;
// For non-negative values:
auto roundup_div( const int64_t a, const int64_t b )
-> int64_t
{ return (a + b - 1)/b; }
} // namespace cppx
namespace int40 {
using cppx::Byte;
using cppx::Index;
using cppx::Size;
using cppx::roundup_div;
using std::vector;
STATIC_ASSERT( CHAR_BIT == 8 );
STATIC_ASSERT( sizeof( int64_t ) == 8 );
const int bits_per_value = 40;
const int bytes_per_value = bits_per_value/8;
struct Packed_values
{
enum{ n = sizeof( int64_t ) };
Byte bytes[n*bytes_per_value];
auto value( const int i ) const
-> int64_t
{
int64_t result = 0;
for( int j = bytes_per_value - 1; j >= 0; --j )
{
result = (result << 8) | bytes[i*bytes_per_value + j];
}
const int64_t first_negative = int64_t( 1 ) << (bits_per_value - 1);
if( result >= first_negative )
{
result = (int64_t( -1 ) << bits_per_value) | result;
}
return result;
}
void set_value( const int i, int64_t value )
{
for( int j = 0; j < bytes_per_value; ++j )
{
bytes[i*bytes_per_value + j] = value & 0xFF;
value >>= 8;
}
}
};
STATIC_ASSERT( sizeof( Packed_values ) == bytes_per_value*Packed_values::n );
class Packed_vector
{
private:
Size size_;
vector<Packed_values> data_;
public:
auto size() const -> Size { return size_; }
auto value( const Index i ) const
-> int64_t
{
const auto where = div( i, Packed_values::n );
return data_[where.quot].value( where.rem );
}
void set_value( const Index i, const int64_t value )
{
const auto where = div( i, Packed_values::n );
data_[where.quot].set_value( where.rem, value );
}
Packed_vector( const Size size )
: size_( size )
, data_( roundup_div( size, Packed_values::n ) )
{}
};
} // namespace int40
#include <iostream>
auto main() -> int
{
using namespace std;
cout << "Size of struct is " << sizeof( int40::Packed_values ) << endl;
int40::Packed_vector values( 25 );
for( int i = 0; i < values.size(); ++i )
{
values.set_value( i, i - 10 );
}
for( int i = 0; i < values.size(); ++i )
{
cout << values.value( i ) << " ";
}
cout << endl;
}
Да, вы можете это сделать, и это сэкономит некоторое пространство для больших количеств чисел
Вам нужен класс, содержащий std::vector целочисленного типа без знака.
Вам понадобятся функции-члены для хранения и извлечения целого числа. Например, если вы хотите сохранить 64 целых числа по 40 бит, используйте вектор из 40 целых чисел по 64 бит. Затем вам нужен метод, который хранит целое число с индексом в [0,64] и метод для получения такого целого.
Эти методы будут выполнять некоторые операции сдвига, а также некоторые бинарные | и.
Я еще не добавляю подробностей здесь, потому что ваш вопрос не очень специфичен. Знаете ли вы, сколько целых чисел вы хотите сохранить? Вы знаете это во время компиляции? Знаете ли вы, когда начинается программа? Как целые числа должны быть организованы? Как массив? Как карта? Вы должны знать все это, прежде чем пытаться сжать целые числа в меньшую память.
Это требует потокового сжатия без потерь. Если это для приложения Big Data, плотные уловки в упаковке - это тактические решения в лучшем случае для того, что, как представляется, требует достаточно приличного промежуточного программного обеспечения или поддержки на системном уровне. Они нуждаются в тщательном тестировании, чтобы убедиться, что вы можете восстановить все биты целыми и невредимыми. И последствия производительности весьма нетривиальны и очень зависят от оборудования из-за помех в архитектуре кэширования процессора (например, кэш-строки и структура упаковки). Кто-то упомянул сложные сетчатые структуры: их часто настраивают на сотрудничество с конкретными архитектурами кэширования.
Из требований не ясно, нужен ли ОП произвольный доступ. Учитывая размер данных, скорее всего, нужен только локальный случайный доступ на относительно небольших фрагментах, организованных иерархически для извлечения. Даже аппаратное обеспечение делает это при больших размерах памяти (NUMA). Как показано в форматах фильмов без потерь, должно быть возможно получить произвольный доступ в кусках ( "кадры" ), не загружая весь набор данных в горячую память (из сжатого хранилища резервной копии в памяти).
Я знаю одну быструю систему баз данных (kdb из KX Systems, чтобы назвать ее, но я знаю, что есть другие), которая может обрабатывать чрезвычайно большие массивы данных, невзирая на массивные массивы данных, хранящиеся в хранилищах памяти. Он имеет возможность прозрачного сжатия и расширения данных "на лету".
Здесь представлено немало ответов, посвященных реализации, поэтому я хотел бы поговорить об архитектуре.
Мы обычно расширяем 32-битные значения до 64-битных значений, чтобы избежать переполнения, потому что наши архитектуры предназначены для обработки 64-битных значений.
Большинство архитектур предназначены для работы с целыми числами, размер которых равен 2, потому что это значительно упрощает аппаратное обеспечение. Задачи, такие как кеширование, намного проще: существует большое количество операций делений и модулей, которые могут быть заменены на маскирование бит и сдвиги, если вы придерживаетесь степеней 2.
В качестве примера того, насколько это важно, спецификация С++ 11 определяет многопоточные расы, основанные на "ячейках памяти". Расположение памяти определено в 1.7.3:
Место памяти является либо объектом скалярного типа, либо максимальным последовательность смежных бит-полей, имеющих отличную от нуля ширину.
Другими словами, если вы используете битовые поля С++, вы должны тщательно выполнять всю свою многопоточность. Два соседних битовых поля должны рассматриваться как одно и то же место памяти, даже если вы хотите, чтобы вычисления по ним могли быть распределены по нескольким потокам. Это очень необычно для С++, поэтому вы можете вызвать разочарование разработчика, если вам нужно беспокоиться об этом.
Большинство процессоров имеют архитектуру памяти, которая извлекает 32-битные или 64-битные блоки памяти за раз. Таким образом, использование 40-битных значений будет иметь удивительное количество дополнительных обращений к памяти, что резко влияет на время выполнения. Рассмотрите проблемы выравнивания:
40-bit word to access: 32-bit accesses 64bit-accesses
word 0: [0,40) 2 1
word 1: [40,80) 2 2
word 2: [80,120) 2 2
word 3: [120,160) 2 2
word 4: [160,200) 2 2
word 5: [200,240) 2 2
word 6: [240,280) 2 2
word 7: [280,320) 2 1
В 64-битной архитектуре один из каждых 4 слов будет "нормальной скоростью". Остальное потребует получения в два раза больше данных. Если вы получите много промахов в кеше, это может привести к снижению производительности. Даже если вы получаете кеш-хиты, вам придется распаковать данные и переупаковать их в 64-битный регистр, чтобы использовать его (что может даже включать в себя трудно предсказать ветку).
Возможно, это стоит затрат
Существуют ситуации, когда эти штрафы являются приемлемыми. Если у вас есть большой объем данных с резидентной памятью, которые хорошо индексируются, вы можете найти экономию памяти, соответствующую штрафу за производительность. Если вы выполняете большое количество вычислений по каждому значению, вы можете найти, что затраты минимальны. Если это так, не стесняйтесь реализовать одно из вышеуказанных решений. Однако, вот несколько рекомендаций.
Если вам действительно нужен массив из 40 битных целых чисел (что, очевидно, не может быть), я бы просто объединил один массив из 32 бит и один массив из 8-битных целых чисел.
Чтобы прочитать значение x в индексе i:
uint64_t x = (((uint64_t) array8 [i]) << 32) + array32 [i];
Чтобы записать значение x в индекс i:
array8 [i] = x >> 32; array32 [i] = x;
Очевидно, красиво инкапсулирован в класс, используя встроенные функции для максимальной скорости.
Есть одна ситуация, когда это субоптимально, и именно тогда вы действительно произвольно получаете доступ ко многим элементам, так что каждый доступ к массиву int будет отсутствовать в кэше - здесь вы каждый раз получаете два промаха в кэше. Чтобы избежать этого, определите 32-байтовую структуру, содержащую массив из шести uint32_t, массив из шести uint8_t и два неиспользуемых байта (41 2/3 бит на число); код для доступа к элементу немного сложнее, но оба компонента элемента находятся в одной строке кэша.