выделение памяти и ее освобождение

[Артэс]

Здравствуйте. Интересует реализация очереди сообщений.

Самое простое - это создать массив указателей

char *msg[100];

и помещать туда сообщения, путем выделения памяти под них.. например, первое сообщение 150 байт, выделяем 150 байт для msg[0].. второе сообщение длиной 500 байт, выделяем 500 байт для msg[1] и так далее..

далее в цикле идет обработка сообщений. Когда 1-ое сообщение обработано, освобождаем память через free(msg[0]); и делаем смещение очереди вперед, т.е. схематически так:

msg[0] = msg[1];
msg[1] = msg[2];
...

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

[Luuzuk]

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

[Abstraction]

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

[Артэс]

При создании статичного массива, делать смещение затратно.. надо "перегнать" все байты на "шаг" вперед. Потому и придумал смещение по указателям. Такая реализация со смещением вперед, кажется мне логичной и простой. Очередь продвигается автоматически. Цикл с обработкой очереди сообщений будет работать все время, пока работает программа... примерно 10 - 20 сообщений в секунду, а может и 30.. все это динамично и зависит от конкретной загруженности очереди в момент времени. Значит 10 - 20 или 30 раз в секунду и выделение / освобождение памяти (это я привел пример, чтобы показать интенсивность планируемого выделения / освобождения памяти, для оценки нагрузки программы на компьютер).

Была идея и о статическом выделении массива под сообщения, например char msg[1024][100]; и указателям выдавать области этого массива. Удалять данные не придется, ибо запись новых автоматически затрет старые. Будет очередь указателей, но уже без освобождения или выделения памяти. Остается добавить цикл, который будет искать по индексу массива сообщений, ненужные сообщения, и выдавать эти строки указателям, для размещения новых сообщений. Но все это мне показалось "замутным", и работа с выделением / освобождением памяти на этом фоне выглядит проще и удобнее... поясните пожалуйста. Какой алгоритм будет выгоднее, учитывая скорость обработки сообщений (как я уже писал, выделение памяти и освобождение 10-20 или 30 раз в секунду).

Добавил позже:

Знаете, написав про обработку сообщений 10-20 или 30 раз в секунду, я забыл о том, что это правильно для 1 или 2 клиентов (клиент-серверное приложение), но если онлайн состоит из 50 клиентов одновременно? Для каждого персонально надо обработать очередь, а это уже сотни сообщений за секунду, а если взять 20 * 50, то выходит даже 1000

[Abstraction]

Простейшая реализация очереди конечной ёмкости:

char* messages[MAX_MESSAGES]; //Никаких волшебных чисел в коде!
size_t firstMessage = 0;
size_t beyondLastMessage = 0;
//Запись
char* messageToWrite = GetMessage();//Будем считать, что память выделяется тут
messages[beyondLastMessage] = messageToWrite;
beyondLastMessage = (beyondLastMessage+1)%MAX_MESSAGES;

//Проверка на пустоту очереди
if(firstMessage == beyondLastMessage) //...
//Проверка на переполненность очереди
if((firstMessage-beyondLastMessage)%MAX_MESSAGES == 1) //...

//Чтение
ProcessMessage(messages[firstMessage]);
delete[] messages[firstMessage];
firstMessage = (firstMessage+1)%MAX_MESSAGES;

Как-то так...

[Артэс]

Да с реализацией проблем нет, я знаю, как это оформить Интересует лишь метод. Значит выделение / освобождение памяти (пусть объемы даже малые), 500-1000 раз в секунду, весьма затратно?

[Abstraction]

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

[Артэс]

Хм, а если задать статичный массив размером 1024x100

char msg[1024][100];

то при обращении к элементам двумерного массива, типа msg[0] или msg[99], вычисление их адреса происходит все-равно быстрее, чем было бы с выделением и освобождением памяти? Массив то не маленький получается.

[waleri]

Сообщение от Артэс

Значит выделение / освобождение памяти (пусть объемы даже малые), 500-1000 раз в секунду, весьма затратно?

Что по вашему "весьма затратно"?
На копирование елементов очереди у вас будет уходить больше времени.
Если хотите конкретный ответ - задайте конкретный вопрос.
В этом плане - выделяйте память и не парьтесь. Если что, существуют профайлеры.

[Abstraction]

Сообщение от Артэс

Хм, а если задать статичный массив размером 1024x100

char msg[1024][100];

то при обращении к элементам двумерного массива, типа msg[0] или msg[99], вычисление их адреса происходит все-равно быстрее, чем было бы с выделением и освобождением памяти? Массив то не маленький получается.

Переход по (любому) индексу - это одна команда процессора, если грубо. Быстрее некуда.