Адекватная замена для MS STL deque?, нужна замена в связи с багой в MS STL Опции Подписка на тему Сообщить другу Версия для печати Скачать тему Подписка на этот форум Режимы отображения Переключить на: Древовидный Переключить на: Стандартный Линейный

[Iron Bug]

В связи с обнаружившейся страшной багой ищу какую-нибудь опенсорцную реализацию дека (ну или хотя бы очереди с итератором или оператором []).

Поиск по гуглу пока не дал ничего вразумительного (слишком распространённое название - deque), а свой огород городить банально не хватает времени... Конечно, если не найду, то придётся возиться с динамическими массивами, а у меня ещё дофига другой работы, причём довольно срочной.
Может, кто подскажет такую готовую библиотечку на С++ или С?

[Алексей1153]

а какие основные плюсы использования дека ? (не довелось пользоваться ни разу - всегда вектора указателей хватало на всё)

Сообщение отредактировал Алексей1153 - 6.10.2010, 13:52

[Iron Bug]

а какие основные плюсы дека ? (не довелось пользоваться ни разу - всегда вектора указателей хватало на всё)

push/pop с двух сторон, итераторы. дек пошустрее вектора и лучше работает с памятью(это эмпирическое наблюдение, как они реализованы, я не смотрела).
не хочу переходить на вектор, он не чистит пространство, которое сожрал, пока не наступит нехватка памяти. а у меня объём данных может накапливаться весьма нехилый и скорость критична. а дек вроде получше себя ведёт. не замечала за ним жрачки памяти и тормозов особых.
конечно, в крайнем случае можно влепить вектор, но не радует такая перспектива. да и не везде можно перейти - у меня часто используется push/pop c головы.


Сообщение отредактировал Iron Bug - 6.10.2010, 14:03

[Алексей1153]

он не чистит пространство, которое сожрал

ну, периодически можно совершать принудительную очистку. Например, если был поюзан объём данных больше заданной величины. Заодно и дефрагментация озу меньше будет.

За скорость не знаю. Но временно в обёртке можно класс-замену сделать и на векторе

Сообщение отредактировал Алексей1153 - 6.10.2010, 14:04

[Iron Bug]

ну, периодически можно совершать принудительную очистку. Например, если был поюзан объём данных больше заданной величины. Заодно и дефрагментация озу меньше будет.

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

Сообщение отредактировал Iron Bug - 6.10.2010, 14:34

[Алексей1153]

STL не очищает её даже когда вектор был очищен явным вызовом clear()

я не про clear, а про явную очистку объекта
m_vec=std::vector();
А clear() - он тем и удобен (в некоторых случаях), что не вызывает реаллокацию.

[Iron Bug]

Нашла кое-какие опенсорцные STL библиотеки:
http://www.thefreecountry.com/sourcecode/cpp.shtml#stl
Сейчас буду смотреть, что они предоставляют.

я не про clear, а про явную очистку объекта

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

[Алексей1153]

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

да блин фантастика какая то ) Надо будет поэкспериментировать на досуге

[kwisp]

Iron Bug,
есть еще реализация stl на сайте sgi и stlPort погугли на эту тему.
теоретически очередь от вектора отличается лишь началом идентичным концу вектора. т.е. быстрая вставка изЪятие и в начале и в конце. память выделяется страницами, и очереди нужен дополнительный указатель на страницу. еще двусторонняя очередь deque - единственные стандартный контейнер STL в котором итераторы могут стать недействительными при действительных указателях и ссылках, об этом Меерс пишет немного.

почему ты решила что очередь пошустрее вектора не пойму (

[Iron Bug]

да блин фантастика какая то ) Надо будет поэкспериментировать на досуге

Вот простой код. Понаблюдай за распределением памяти при работе. (Естественно, речь про MS STL, чтобы никто не понял неправильно).

Раскрывающийся текст

#include "windows.h"
#include <vector>
#include <iostream>

int main()
{
    for(int i=0; i< 1000000; i++)
    {
        std::vector<int> v;
        for(int j=0; j< 1000000; j++)
        {
            v.push_back(j);
        }
        std::cout << i << std::endl;
        Sleep(100);
    }
}

И можешь туда хоть clear вставлять, хоть любую "очистку". Не канает!
А если убрать слип (он вставлен для наглядности) и добавить объёма - то будет расти метров до 500 в памяти свободно. И потом разом чиститься, по неизвестно каким соображениям. Я же не просто так утверждаю, что такая "фича" существует, а потому что напоролась на неё при работе и ушла от активного использования векторов. плюс тормоза. это тоже при работе на больших объёмах было выявлено экспериментально.

Сообщение отредактировал Iron Bug - 6.10.2010, 15:06

[kwisp]

Iron Bug,
попробовал твой пример в linux - память выше 5М не растет и очищается периодически. может все же это конкретная реализация так себя ведет.
конечно вектор при таком использовании будет оч медленно заполнятся - каждый push_back - куча лишних операций по перераспределению ,выделению, копированию.

[Iron Bug]

попробовал твой пример в linux

я пишу конкретно про MS STL
в линюксе проблем вообще нет. ну или редко и их быстро правят а мелкософт пока разродится с новой студией с этим патчем - сто лет пройдёт.

Сообщение отредактировал Iron Bug - 6.10.2010, 15:36

[kwisp]

я пишу конкретно про MS STL

я чет сразу не увидел

(Естественно, речь про MS STL, чтобы никто не понял неправильно).

хм...
MS STL - понятно, ну тут как говорится доверяй но проверяй. )

[Iron Bug]

ну тут как говорится доверяй но проверяй. )

вот и проверили мне ещё разработчики буста не поверили (я сначала думала, что это глюк буста и написала в рассылки буста), пока David Ward не написал про багу (он её и нашёл, кстати, причём в феврале этого года, судя по дате заявки). а все эти годы никто не замечал. а мне наши механики (которые юзают много всяких моих софтин для управления механизмами) иногда говорили, что прога падает без причины. я ничего подозрительного не могла найти. а вот сейчас я перешмонаю все свои проги на предмет этой шняги. уже нашла три довольно критических проекта, в которых deque заюзан. скорости там поменьше - поэтому ошибки случаются значительно реже. видимо, как-то так. у меня только в юзерских интерфейсах STL юзается, к счастью. железо из-за этого не ломалось
и вот сейчас вклинилась совершенно не к месту задача мелкой правки всего нажитого праведным трудом

Сообщение отредактировал Iron Bug - 6.10.2010, 15:51

[Алексей1153]

конечно вектор при таком использовании будет оч медленно заполнятся - каждый push_back - куча лишних операций по перераспределению ,выделению, копированию.

просто об этом надо заранее думать, вот и всё. Резервировать же можно кусками

Iron Bug, выполнил предложенный код. У меня на борту всего 640 метров озу, в момент начала запуска теста занято было 560 (смотрю диспетчером). Во время выполнения меняется от 560 до 562 , иногда прыгало до 568 - у меня ещё радива играет. Ничего не тормозит и память не жрётся, своп тоже молчит. Пробую в студии №6 , кстати.

Щас попробую в 2008

- во время запуска 631 , скачет 632... 635, без свопа, без тормозов

правда, это всё в дебаге было. Имеет значение ?

в релизе тоже память не жрётся

[Iron Bug]

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

просто об этом надо заранее думать, вот и всё. Резервировать же можно кусками

а резервировать кусками не выходит - у меня никогда не известно, какой буфер накопится до момента, когда проснётся сливающий данные поток. это зависит от того, что будет выплёвывать хард и как будет нагружен проц. так что там заранее ничего нельзя предсказать. пишут несколько потоков, сливает один. при таком раскладе заранее планировать ничего невозможно.
можно было бы кое-где заменить deque на queue, но в остальных случаях мне ещё нужны итераторы. а тут queue уже не проканает.

собственно, раз там всё равно баги, я планирую помаленьку перейти на опенсорцный STL и не парить себе моск. так оно надёжнее и ещё минус одна зависимость от мелкософта, который я терпеть не могу

Сообщение отредактировал Iron Bug - 6.10.2010, 22:19

[Алексей1153]

и ещё минус одна зависимость от мелкософта,

та ну, неспортивно

шутка.

[AD]

собственно, раз там всё равно баги, я планирую помаленьку перейти на опенсорцный STL и не парить себе моск. так оно надёжнее и ещё минус одна зависимость от мелкософта, который я терпеть не могу

Я немного чайник в этом. Тема крайне заинтересовала (есть проект, жутко страдающий из-за низкой эффективности). Пара вопросов: как именно перейти с MS STL на Open-Source STL? Чем они в плане возможностей будут отличаться в контексте данной проблемы?

Сообщение отредактировал AD - 7.10.2010, 7:59

[Iron Bug]

я пока не утверждала, что опенсорцный STL эффективнее (хотя скорее всего так оно и есть). но если в MS STL жёсткие баги, то использовать его просто нельзя. тут не до эффективности, когда прога валится с access violation.
сейчас вот как раз пытаюсь собрать один STL.

[AD]

Блин. Где собрать? Как подключить? Внешне отличаться он не будет?

[Iron Bug]

Блин. Где собрать? Как подключить? Внешне отличаться он не будет?

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

[Iron Bug]

Ура! Я собрала STLport с бустом под студией 2005.

Пишу маленькую инструкцию:

Сборка STLport + Boost компилятором MSVC 2005

(я собирала с версиями STLport 5.2.1, Boost 1.44.0, MSVS 2005 SP1)

1. Качаем последнюю версию буста тут. Разворачиваем куда-либо. Допустим, пускай это будет папка c:/src/boost_1_44_0. Оттуда же качаем уже собранный bjam и помещаем bjam.exe в корневую папку с бустом (вообще, он поставляется прямо с бустом и можно его самостоятельно собрать, запустив bootstrap в корневом каталоге буста).

2. Качаем последнюю версию STLport тут. Разворачиваем куда-либо. Допустим, пускай это будет папка c:/src/STLport-5.2.1.

3. Собираем буст с заголовками STLPort:
3.1. В каталоге c:/src/boost_1_44_0/tools/build/v2 правим файл user-config.jam. Добавляем строку с указанием расположения заголовочных файлов STLport:

using stlport : 5.2.1 : с:/src/STLPort-5.2.1/stlport ;

Пробел перед завершающим символом ";" обязателен! (блок code убивает пробелы - так что вставляю в quote)
(Буст добавляет букву p к именам библиотек, которая означает, что данная сборка собрала с STLport. Так что сборка безопасна, если у вас собраны другие варианты библиотеки).

3.2. Из корневого каталога буста (там уже лежит bjam.exe) запускаем bjam c нужными нам параметрами. Например, для полной сборки буста это будет такая строка:

bjam stdlib=stlport --toolset=msvc-8.0 --build-dir="папка, где будут храниться временные файлы во время сборки" --build-type=complete "путь, куда буст будет складывать готовые файлы"

Обратите внимание, добавлена опция stdlib=stlport - это и есть указание использовать наш STLport.
Запускаем bjam и идём отдыхать: собирается он долго и нудно. Чтобы было быстрее, можете добавить в строку опцию -jN, где N - количество ядер CPU у вас на компе - тогда он будет распараллеливать процесс сборки. Можете запустить bjam --help и посмотреть другие параметры: например, можно указать, куда конкретно складывать заголовки и библиотеки, и прочие такие полезные опции.

4. Собираем сам STLport:
4.1. Открываем консоль (cmd). Запускаем установку переменных окружения MSVC 2005. Если студия установлена в стандартном варианте, с 32-битной платформой, то это будет выглядеть так:

"С:\Program Files\Microsoft Visual Studio 8\VC\bin\vcvars32.bat"

4.2. Далее НЕ ВЫХОДЯ из консоли, перемещаемcя в ней к нашей папке с STL (cd c:/src/STLport-5.2.1) и в этой папке выполняем следующую команду:

configure msvc8 --with-static-rtl

Я собирала со статической линковкой стандартных библиотек. Можете использовать динамическую, заменив опцию на --with-dynamic-rtl.
4.3. НЕ ВЫХОДЯ из консоли, переходим в каталог c:/src/STLport-5.2.1/build/lib и запускаем там команду

nmake /fmsvc.mak install

Ждём, когда скомпилится. Детально про сборку и возможности проверки собранного STLport можно почитать в файле c:/src/STLport-5.2.1/doc/README.msvc (правда, там опечатка с указанием опции компилятора - он задаётся без префикса -c).

5. Открываем студию и прописываем в студии пути для нашего STL: меню Tools->Options. Настройка VC++ Directories:
Platform: Win32, Show directories for: Include files - добавить ПЕРЕД всеми стандартными путями путь c:/src/STLport-5.2.1/stlport
Platform: Win32, Show directories for: Library files - добавить ПЕРЕД всеми стандартными путями путь c:/src/STLport-5.2.1/lib

Собственно, всё.

Код править не нужно, насколько я понимаю. У меня deque заработал без проблем. Просто перекомпиляция.

P.S. Теоретически, можно собирать и без буста.

P.P.S. Если вдруг кто-то захочет собрать и что-то вдруг не будет собираться - сообщайте. Я могла что-то упустить, хотя вроде бы всё написала и порядок не перепутала.

Сообщение отредактировал Iron Bug - 7.10.2010, 15:47

[Iron Bug]

Чуть поторопилась я с вариантом сборки STLport c бустом: он не собирается с ходу с новыми бустами. Однако, это не мешает собирать буст с самим STLport и писать проги с использованием STLport и boost.
Сам STLport из буста юзает только type_traits, это не критичная фича. Так, сбоку бантик. В новых бустах там не много изменилось: пару заголовков переместили. Может, попозже напишу патч для STL, чтобы он собирался с новым бустом, если будет время.
Инструкцию чуть подправила по этому поводу, в остальном вроде всё правильно. Только что собрала другую версию буста с STL. Сейчас буду пересобирать и проверять свои глобальные проекты, которые активно юзают разные фичи STL.

А я тем временем собрала то же самое под линём, с gcc. Скорее из любопытства, чем по необходимости. Пока ещё не проверяла компиляцию с проектами, но буст уже собрался. Надо сказать, что в венде эту связку собрать - это ещё цветочки! Под линём косяков с нестковкой буста и STLport было больше, а документации практически нет. Если эта химия заработает и кому-то понадобится вдруг - могу накатать аналогичную телегу и для линя. Хотя это геморно весьма: там стопицот мелких настроек там и тут. Но если заработает - я погоняю тесты на скорость. Про венду в инете пишут, что с STLPort проги быстрее робят. Надо проверить и под линюксом, ради интереса.

Сообщение отредактировал Iron Bug - 7.10.2010, 22:10

[Iron Bug]

В общем, под вендой у меня всё заработало.
Есть некоторые тонкости, которые сразу просечь трудновато.
Во-первых, практически вся конфигурация STLport фактически задаётся в файле STLport-x.x.x/stlport/stl/config/user_condig.h.
Во-вторых, чтобы эта настройка через файл подействовала, надо обязательно пересобрать STLport с опцией clean:

nmake /fmsvc.mak clean install

Без clean он тупо переименовывает библиотеки и в итоге получается бардак.
Со статической/динамической линковкой я разобралась, но это дофига информации. Вроде там всё логично, но весьма трудно для изложения в единой связке и долго. Поэтому если будут какие вопросы - пишите сюда, попробую ответить.

Сообщение отредактировал Iron Bug - 8.10.2010, 9:52

[Iron Bug]

Аццкая жесть или как под вендой заставить STLport выводить в консоль русские буквы (ну или какие-либо, которые в коде присустствуют) в UTF-8 (убила целый день, чтобы просечь, как это сделать!). Суть была в том, чтобы не переписывать кучу проектов под STLport iostreams.

Частично стащено отсюда, поправлены ошибки и выдернута часть только для венды (для линя и так всё работает, без особого выпендрёжа). Честно говоря, вдаваться в тонкости и разбираться во всех хитросплетениях локалей (а это самое моё ненавистное место в программах!) мне не хотелось. Это решение маленькое, возможно, не самое оптимальное, но оно РАБОТАЕТ.

Раскрывающийся текст

#include <Windows.h>
#include <iostream>
#include <locale>
#include <set>
#include <stdexcept>
#include <stdio.h>

using namespace std;

void configure_locale() {
    //Decoding of wchar in output only happens in unsynced mode.  
    ios::sync_with_stdio(false);
    //Platform dependent locale name building. Needed only for output encoding. 
    char localeString[200];

    const int bufferLength=100;
    char buffer[bufferLength];
    // Obtaining user language
    long rc=GetLocaleInfo(GetUserDefaultLCID(), LOCALE_SISO639LANGNAME, (LPWSTR)buffer, bufferLength);
    
    //Checking for errors. Error codes taken from MSDN. Neither of them happened earlier. 
    if (!rc) {
        switch (GetLastError()) {
        case ERROR_INSUFFICIENT_BUFFER:
            throw runtime_error("Insufficient buffer size while retrieving language info");
        case ERROR_INVALID_FLAGS:
            throw runtime_error("Invalid flags while retrieving language info");
        case ERROR_INVALID_PARAMETER:
            throw runtime_error("Invalid parameter while retrieving language info");
        default:
            throw runtime_error("Unknown error while retrieving language info");
        }
    }
    // Obtaining codepage. In sltport we may also use a string "OCP" instead of value returned by GetConsoleOutputCP().
    long cpInt=GetConsoleOutputCP();
    sprintf_s(localeString,100,"%ws.%d",buffer,cpInt);

    //A new short locale name is built. We can use it to init encoding conversions.
    typedef codecvt<wchar_t, char, mbstate_t> Code;
    Code * code=new codecvt_byname<wchar_t, char, mbstate_t>(localeString);
    //Resetiing global locale object.
    locale::global(locale(locale(localeString), code));
    //We should imbue new locale in iostreams.
    typedef set<wostream::_Basic_ios  *> Streams;
    Streams streams;
    streams.insert(&wcout);
    streams.insert(&wcerr);
    streams.insert(&wclog);
    streams.insert(&wcin);
    for (Streams::iterator i=streams.begin(); i!=streams.end(); i++) {
        if (!(*i))
            continue;
        (*i)->imbue(locale());
        (*i)->rdbuf()->pubimbue(locale());
    }
}

Используется просто вызовом

_wsetlocale(LC_ALL,L"russian");
configure_locale();

перед началом работы. Собирается с опциями использования юникода.
Вывод стандартный:

wcout << L"Русский текст";

Сообщение отредактировал Iron Bug - 11.10.2010, 14:21