С++: Уменьшение памяти в 8 раз

[Day]

Zealint в сообщении #541492 писал(а):

(едва ли когда-нибудь long с языке C станет больше 4 байт).

Увы! На 64-разрядном хосте, при компиляции gcc, long оказался 8-ми байтовым. Намучился я с ним изрядно. Дело в том, что данные в файлах были рассчитаны на 4-х байтовый long

[Alexu007]

Zealint в сообщении #541492 писал(а):

На самом деле в случае с char может получиться ерунда. Вообще-то он однобайтовый. Но он на то и символьный, что может однажды стать двухбайтовым, как int из 2 байт однажды стал 4...

Есть тип __int8 и он уж точно не станет 16-битным (для этого ему надо потеснить __int16). А вообще это свойство процессора - работать с данными порциями по 8 бит, так что байту до появления первых квантовых компьютеров ничего не грозит.

Цитата:

...А ещё для решения указанной задачи можно забить на решето и решать по-другому.

Есть много задач, когда в массивы записываются только 0 и 1. Например получить пару миллиардов неповторяющихся случайных чисел. Работа с битами - уменьшение требуемой памяти в 8 раз - может оказаться неплохим решением.

[nestoklon]

Alexu007 в сообщении #541521 писал(а):

А вообще это свойство процессора - работать с данными порциями по 8 бит

Ну, уже лет 20 как его свойство работать с данными порциями по 32 бита...

[Alexu007]

nestoklon в сообщении #541524 писал(а):

Ну, уже лет 20 как его свойство работать с данными порциями по 32 бита...

Может я неправильно сформулировал? Минимальная порция данных - 8 бит = 1 байт. Процессор не может переписать выборочно 1 или 2 бита, он может переписать только весь байт целиком. Возможно это и не лучшее решение, но оно было принято, и поменять его сегдня = выбросить на помойку весь имеющийся софт.

[Day]

pika в сообщении #540319 писал(а):

нужно уменьшить размер массива в 8 раз, я понимаю, что нужно обращаться к битам, но не могу реализовать.

А кто вам мешает уменьшить размер массива не в 8, а в 30 раз?
После 30 простые числа дают остаток от деления на 30 - 1, 7, 11, 13, 17, 19, 23, 29. - ровно 8 штук, вот ведь везуха! Ну и рассматривать числа "тридцатками" На каждую тридцатку - 8 битов = 1 байт

[venco]

Zealint в сообщении #541492 писал(а):

(едва ли когда-нибудь long с языке C станет больше 4 байт).

Уже.
В 64-битном режиме часто 64-битным делают именно long, а int оставляют 32 бита.

-- Ср фев 22, 2012 07:52:18 --

Alexu007 в сообщении #541533 писал(а):

nestoklon в сообщении #541524 писал(а):

Ну, уже лет 20 как его свойство работать с данными порциями по 32 бита...

Может я неправильно сформулировал? Минимальная порция данных - 8 бит = 1 байт. Процессор не может переписать выборочно 1 или 2 бита, он может переписать только весь байт целиком.

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

[Zealint]

Day в сообщении #541498 писал(а):

Zealint в сообщении #541492 писал(а):

(едва ли когда-нибудь long с языке C станет больше 4 байт).

Увы! На 64-разрядном хосте, при компиляции gcc, long оказался 8-ми байтовым. Намучился я с ним изрядно. Дело в том, что данные в файлах были рассчитаны на 4-х байтовый long

venco в сообщении #541577 писал(а):

Уже.
В 64-битном режиме часто 64-битным делают именно long, а int оставляют 32 бита.

Да, неожиданно. Но идея моя в том, чтобы найти такой тип, который точно не поменяется. Вот мне подсказывают __int8, но он не везде есть. Лучше определить свой тип MyInt32 и потом подставлять в него именно то, что будет гарантированно 32 битовым. А вообще нарушение совместимости немного раздражает, поэтому я во многих важных программах всегда определяю свои типы данных. При переносе программы просто меняю преамбулу файла.

[Alexu007]

venco в сообщении #541577 писал(а):

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

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

Какие там у вас команды для оперирования битами прямо в памяти? И как адресация осуществляется? Может я отстал от жизни?

-- Ср фев 22, 2012 19:52:18 --

Zealint в сообщении #541628 писал(а):

...Лучше определить свой тип MyInt32 и потом подставлять в него именно то, что будет гарантированно 32 битовым. А вообще нарушение совместимости немного раздражает, поэтому я во многих важных программах всегда определяю свои типы данных. При переносе программы просто меняю преамбулу файла.

Круто! А хоть арифметические операции для своего типа работать будут, или нужно будет самому вручную переписывать всё, начиная с А + В?

[venco]

Alexu007 в сообщении #541635 писал(а):

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

Какие там у вас команды для оперирования битами прямо в памяти? И как адресация осуществляется? Может я отстал от жизни?

Чтобы поменять байт в памяти, современный процессор читает 64-байтовую строку кеша, а потом пишет её целиком назад. Полная аналогия с модификацией одного бита. А для битов и команды есть в i386: bt, btc, bts, btr.

-- Ср фев 22, 2012 11:03:16 --

Alexu007 в сообщении #541635 писал(а):

Круто! А хоть арифметические операции для своего типа работать будут, или нужно будет самому вручную переписывать всё, начиная с А + В?

Под определением своего типа Zealint, скорее всего, имел в виду typedef - синоним существующего типа вместе со всеми его функциями и операторами.

[Zealint]

venco в сообщении #541638 писал(а):

Под определением своего типа Zealint, скорее всего, имел в виду typedef - синоним существующего типа вместе со всеми его функциями и операторами.

Да, именно так имело в виду здесь.

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

-- Ср фев 22, 2012 20:05:08 --

Вот пример заготовки, которая меня последние несколько лет полностью устраивает. Слово signed добавил лишь из эстетического чувства, заставшего меня в момент написания кода.

   typedef signed char      int8;
   typedef signed short int int16;
   typedef signed int       int32;
#if defined(__GNUC__)
   typedef signed long long int64;  
#else
   typedef signed __int64   int64;  
#endif

   typedef unsigned char      int8u;
   typedef unsigned short int int16u;
   typedef unsigned int       int32u;
#if defined(__GNUC__)                 
   typedef unsigned long long int64u;
#else
   typedef unsigned __int64   int64u; 
#endif

[Alexu007]

Day в сообщении #541566 писал(а):

pika в сообщении #540319 писал(а):

нужно уменьшить размер массива в 8 раз, я понимаю, что нужно обращаться к битам, но не могу реализовать.

А кто вам мешает уменьшить размер массива не в 8, а в 30 раз?
После 30 простые числа дают остаток от деления на 30 - 1, 7, 11, 13, 17, 19, 23, 29. - ровно 8 штук, вот ведь везуха! Ну и рассматривать числа "тридцатками" На каждую тридцатку - 8 битов = 1 байт

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

[venco]

Zealint в сообщении #541675 писал(а):

Слово signed добавил лишь из эстетического чувства, заставшего меня в момент написания кода.

На всякий случай: в случае с "signed char" это важно, "signed char" и "char" - разные типы.

-- Ср фев 22, 2012 12:24:50 --

Alexu007 в сообщении #541681 писал(а):

Day в сообщении #541566 писал(а):

pika в сообщении #540319 писал(а):

нужно уменьшить размер массива в 8 раз, я понимаю, что нужно обращаться к битам, но не могу реализовать.

А кто вам мешает уменьшить размер массива не в 8, а в 30 раз?
После 30 простые числа дают остаток от деления на 30 - 1, 7, 11, 13, 17, 19, 23, 29. - ровно 8 штук, вот ведь везуха! Ну и рассматривать числа "тридцатками" На каждую тридцатку - 8 битов = 1 байт

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

Это нетривиальная оптимизация, но экономит не только память, но и рантайм из-за лучшей работы кеша.

[Day]

Alexu007 в сообщении #541681 писал(а):

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

Обещаю, покажу. Это не слишком сложно, но требует некоторого умственного напряжения. Вот, празднички закончатся, или пауза какая образуется...

Всех с наступающим праздником!

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

[Alexu007]

Day в сообщении #541725 писал(а):

Ведь не храните же вы четные позиции. Или все-таки храните

Храним мы только единицы и нули. А само число - это адрес, смещение относительно начала массива. В адресах простых чисел - нули, остальное единицы.

[Day]

Alexu007 в сообщении #541760 писал(а):

Храним мы только единицы и нули. А само число - это адрес, смещение относительно начала массива. В адресах простых чисел - нули, остальное единицы.

Значит по адресу 20223456 вы тоже что-то храните?
Вы там храните единицу, я знаю. А зачем ее хранить? Если даже я знаю, не протряся еще ничего из этого решета.

-- Чт фев 23, 2012 00:47:27 --

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

  A = N/30;
  R = N%30;
  if (R==1) A+=1;
  else if (R==7) A+=2
  else if (R==11) A+=3
  // ......

А остальные значения N нас просто не интересуют, мы априори знаем, что они не просты (простите невольный каламбур)
Все это, конечно, можно оформить и поизящнее, но подождите чуток.