[ATL] Рост CString не экспоненциальный - почему?
От: Alexander G Украина  
Дата: 21.01.10 16:21
Оценка:
Для перераспределения строки при её увеличении для определения размера вновь выделенного блока вызывается следующее:
            // Grow exponentially, until we hit 1K.
            int nNewLength = pOldData->nAllocLength;
            if( nNewLength > 1024 )
            {
                nNewLength += 1024;
            }
            else
            {
                nNewLength *= 2;
            }


Выгоден ли такой подход? Если да, то когда и почему std::vector сделан не так?
Русский военный корабль идёт ко дну!
Re: [ATL] Рост CString не экспоненциальный - почему?
От: remark Россия http://www.1024cores.net/
Дата: 21.01.10 17:12
Оценка: 17 (2)
Здравствуйте, Alexander G, Вы писали:

AG>Выгоден ли такой подход? Если да, то когда и почему std::vector сделан не так?


Лучшего варианта нет. Всё зависит от использования и требований по памяти/скорости.
Я думаю, что разработчики CString и std::vector<> просто ориентировались на различные паттерны использования.

Это неоднократно обсуждалось. Например здесь:
http://www.rsdn.ru/forum/cpp/1806588.aspx
Автор: Дядюшка Че
Дата: 27.03.06


А вот тут предлагается растить размер как 1.32*X
http://rsdn.ru/forum/cpp/2964501.1.aspx
Автор: remark
Дата: 26.05.08



1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re: [ATL] Рост CString не экспоненциальный - почему?
От: MasterZiv СССР  
Дата: 22.01.10 08:50
Оценка:
Alexander G wrote:

> Выгоден ли такой подход? Если да, то когда и почему std::vector сделан

> не так?

Так это зависит от конкретных требований конкретного приложения.
Если ты добавляешь в строку по 1-ому символу -- это одно. Если
добавляешь по 8 килобайт -- это другое.
Posted via RSDN NNTP Server 2.1 beta
Re[2]: [ATL] Рост CString не экспоненциальный - почему?
От: Alexander G Украина  
Дата: 22.01.10 09:43
Оценка:
Здравствуйте, MasterZiv, Вы писали:

>> Выгоден ли такой подход? Если да, то когда и почему std::vector сделан

>> не так?

MZ>Так это зависит от конкретных требований конкретного приложения.

MZ>Если ты добавляешь в строку по 1-ому символу -- это одно. Если
MZ>добавляешь по 8 килобайт -- это другое.

Допустим, у меня документ, состоящий из объектов, содержащих CString, и надо передать выделенную часть в SetClipboardData. И, допустим, копируем в один проход, сразу в CString. Так, размер документа заранее неизвестен и на больших документах число копирований в памяти будет расти линейно от размера документа, т.е. количество скопированных байт — квадратично, даже если добавляемые CString по 8 килобайт.

Т.е. при произвольно больших строках рост по килобайту — невыгоден. Когда выгоден — неясно. Я не вижу большого выигрыша от того, что строка в 1200 символов займёт 3 КБ, а не 4, с учётом потери времени на чуть более длинных строках.
Русский военный корабль идёт ко дну!
Re[3]: [ATL] Рост CString не экспоненциальный - почему?
От: remark Россия http://www.1024cores.net/
Дата: 22.01.10 09:51
Оценка:
Здравствуйте, Alexander G, Вы писали:

MZ>>Так это зависит от конкретных требований конкретного приложения.

MZ>>Если ты добавляешь в строку по 1-ому символу -- это одно. Если
MZ>>добавляешь по 8 килобайт -- это другое.

AG>Допустим, у меня документ, состоящий из объектов, содержащих CString, и надо передать выделенную часть в SetClipboardData. И, допустим, копируем в один проход, сразу в CString. Так, размер документа заранее неизвестен и на больших документах число копирований в памяти будет расти линейно от размера документа, т.е. количество скопированных байт — квадратично, даже если добавляемые CString по 8 килобайт.


Теперь ты знаешь, что CString не предназначен для такого использования

AG>Т.е. при произвольно больших строках рост по килобайту — невыгоден. Когда выгоден — неясно. Я не вижу большого выигрыша от того, что строка в 1200 символов займёт 3 КБ, а не 4, с учётом потери времени на чуть более длинных строках.


Ты тут просто меняешь шило на мыло.
При экспоненциальном росте: количество копирований O(logN), издержки по памяти O(N).
При линейном росте: количество копирований O(N), издержки по памяти O(1).
Я думаю, представить сценарий, когда издержки по памяти O(1) вместо O(N), достаточно просто. CString даёт гарантию, что будет выброшено не более 1кб памяти (!), std::vector же допускает выбрасывание на ветер произвольного кол-ва памяти (мегабайт, 100 мегабайт, гигабайт — сколько угодно... ну, естественно, в зависимости от размера данных). Поэтому говорить о лучшей стратегии тут врядли уместно.


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re: [ATL] Рост CString не экспоненциальный - почему?
От: ononim  
Дата: 22.01.10 10:10
Оценка:
AG>Выгоден ли такой подход? Если да, то когда и почему std::vector сделан не так?
У std::vector по стандарту push_back должен исполнятся за константное амортизированное время
На CString никаких стандартов нету
Кроме того добавление элементов в CString операция обычно более редкая чем добавление в вектор.
Как много веселых ребят, и все делают велосипед...
Re[4]: [ATL] Рост CString не экспоненциальный - почему?
От: Alexander G Украина  
Дата: 22.01.10 10:15
Оценка:
Здравствуйте, remark, Вы писали:

R>Ты тут просто меняешь шило на мыло.

R>При экспоненциальном росте: количество копирований O(logN), издержки по памяти O(N).
R>При линейном росте: количество копирований O(N), издержки по памяти O(1).

Я не совсем понимаю, почему в общем случае (CString же для повсеместного хранения строк) приоритет на экономию памяти. При малых объёмах на результат будет влиять гранулярность кучи, оверхед на блок кучи, фрагментация кучи, в результате выигрыш от такой экономии сомнителен. При больших объёмах речь уже будет идти не о выделенной зря памяти, а о выделенном зря диапазоне в адресном пространстве, физическая память которому не будет сопоставлена, т.к. к нему не будет обращений.

Издержки по памяти O(N) против O(1) будут означать, что приложению может требоваться в К раз больше памяти, К меньше двух. Это не проблема по сравнению с возможным оверхедом на лишние копирования.
Русский военный корабль идёт ко дну!
Re[5]: [ATL] Рост CString не экспоненциальный - почему?
От: remark Россия http://www.1024cores.net/
Дата: 22.01.10 10:33
Оценка: 1 (1)
Здравствуйте, Alexander G, Вы писали:

AG>Я не совсем понимаю, почему в общем случае (CString же для повсеместного хранения строк) приоритет на экономию памяти. При малых объёмах на результат будет влиять гранулярность кучи, оверхед на блок кучи, фрагментация кучи, в результате выигрыш от такой экономии сомнителен. При больших объёмах речь уже будет идти не о выделенной зря памяти, а о выделенном зря диапазоне в адресном пространстве, физическая память которому не будет сопоставлена, т.к. к нему не будет обращений.


AG>Издержки по памяти O(N) против O(1) будут означать, что приложению может требоваться в К раз больше памяти, К меньше двух. Это не проблема по сравнению с возможным оверхедом на лишние копирования.


Откуда такая уверенность?

Я например сейчас работаю с клиентским приложением, в целом все операции достаточно лёгкие и скорость не является проблемой; а вот память как раз является — программа ела в несколько раз больше памяти, чем хотелось бы. В ходе оптимизации, в частности, было сделано, что бы строки выделяли *ровно* столько памяти, сколько нужно + убрана small string optimization (т.е. убран небольшой статический буфер из строк). В результате скорость как была удовлетворительной, так и осталась, а вот память существенно сократилась.
Поэтому для меня лично, это утверждение не столь очевидно.

К тому же сейчас оптимизируя память — оптимизируешь и производительность... но это уже отдельная история.



1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[5]: [ATL] Рост CString не экспоненциальный - почему?
От: MasterZiv СССР  
Дата: 23.01.10 14:55
Оценка:
Alexander G wrote:

> Я не совсем понимаю, почему в общем случае (CString же для повсеместного

> хранения строк) приоритет на экономию памяти. При малых объёмах на

Потому что для реальной оптимизации выделения ты должен вызывать всё
равно GetBuffer/Release. Так к чему весь этот разговор вообще ?
Posted via RSDN NNTP Server 2.1 beta
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.