Как оптимизировать копирование строк (выделение памяти)?

Question

Я делаю программу (подумайте: что-то вроде Launchy ), которая, более или менее, проходит через набор строк и ранжирует их в соответствии с некоторыми критериями.

Я сохраняю результаты в vector<SearchSuggestion>, где структура в настоящее время определяется следующим образом:

struct SearchSuggestion
{
    std::string path;
    int tag;
};

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

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

ntdll.dll!RtlCompareMemoryUlong()   
ntdll.dll!RtlpAllocateHeap()    
ntdll.dll!RtlAllocateHeap()     
ntdll.dll!RtlDebugAllocateHeap()    
ntdll.dll!string "Enabling heap debug options\n"()  
ntdll.dll!RtlAllocateHeap()     
msvcr90d.dll!_heap_alloc_base(unsigned __int64)     C
msvcr90d.dll!_heap_alloc_dbg_impl(unsigned __int64, int, const char *, int, int *)
msvcr90d.dll!_nh_malloc_dbg_impl(unsigned __int64, int, int, const char *, int, int *)
msvcr90d.dll!_nh_malloc_dbg(unsigned __int64, int, int, const char *, int)
msvcr90d.dll!malloc(unsigned __int64)
msvcr90d.dll!operator new(unsigned __int64)
MyProgram.exe!std::_Allocate<wchar_t>(unsigned __int64, wchar_t *)
MyProgram.exe!std::allocator<wchar_t>::allocate(unsigned __int64)
MyProgram.exe!std::basic_string<wchar_t,std::char_traits<wchar_t>,std::allocator<wchar_t> >::_Copy(unsigned __int64, unsigned __int64)
MyProgram.exe!std::basic_string<wchar_t,std::char_traits<wchar_t>,std::allocator<wchar_t> >::_Grow(unsigned __int64, bool)
MyProgram.exe!std::basic_string<wchar_t,std::char_traits<wchar_t>,std::allocator<wchar_t> >::assign(const std::basic_string<wchar_t,std::char_traits<wchar_t>,std::allocator<wchar_t> > &, unsigned __int64, unsigned __int64)
MyProgram.exe!std::basic_string<wchar_t,std::char_traits<wchar_t>,std::allocator<wchar_t> >::basic_string<wchar_t,std::char_traits<wchar_t>,std::allocator<wchar_t> >(const std::basic_string<wchar_t,std::char_traits<wchar_t>,std::allocator<wchar_t> > &)
MyProgram.exe!SearchSuggestion::SearchSuggestion(const SearchSuggestion &)
MyProgram.exe!std::_Construct<SearchSuggestion,SearchSuggestion>(SearchSuggestion *, const SearchSuggestion &)
MyProgram.exe!std::allocator<SearchSuggestion>::construct(SearchSuggestion *, const SearchSuggestion &)
MyProgram.exe!std::_Uninit_copy<SearchSuggestion * __ptr64,SearchSuggestion * __ptr64,std::allocator<SearchSuggestion> >(SearchSuggestion *, SearchSuggestion *, SearchSuggestion *, std::allocator<SearchSuggestion> &, std::_Nonscalar_ptr_iterator_tag, std::_Nonscalar_ptr_iterator_tag)
MyProgram.exe!stdext::unchecked_uninitialized_copy<SearchSuggestion * __ptr64,SearchSuggestion * __ptr64,std::allocator<SearchSuggestion> >(SearchSuggestion *, SearchSuggestion *, SearchSuggestion *, std::allocator<SearchSuggestion> &)
MyProgram.exe!std::_Uninit_move<SearchSuggestion * __ptr64,SearchSuggestion * __ptr64,std::allocator<SearchSuggestion>,std::_Undefined_move_tag>(SearchSuggestion *, SearchSuggestion *, SearchSuggestion *, std::allocator<SearchSuggestion> &, std::_Undefined_move_tag, std::_Undefined_move_tag)
MyProgram.exe!stdext::_Unchecked_uninitialized_move<SearchSuggestion * __ptr64,SearchSuggestion * __ptr64,std::allocator<SearchSuggestion> >(SearchSuggestion *, SearchSuggestion *, SearchSuggestion *, std::allocator<SearchSuggestion> &)
MyProgram.exe!std::vector<SearchSuggestion,std::allocator<SearchSuggestion> >::_Umove<SearchSuggestion * __ptr64>(SearchSuggestion *, SearchSuggestion *, SearchSuggestion *)
MyProgram.exe!std::vector<SearchSuggestion,std::allocator<SearchSuggestion> >::_Insert_n(std::_Vector_const_iterator<SearchSuggestion,std::allocator<SearchSuggestion> > *, unsigned __int64, const SearchSuggestion &)
MyProgram.exe!std::vector<SearchSuggestion,std::allocator<SearchSuggestion> >::insert(std::_Vector_const_iterator<SearchSuggestion,std::allocator<SearchSuggestion> > *, const SearchSuggestion &)
MyProgram.exe!std::vector<SearchSuggestion,std::allocator<SearchSuggestion> >::push_back(const SearchSuggestion &)
MyProgram.exe!Appender<std::vector<SearchSuggestion,std::allocator<SearchSuggestion> > >(const wchar_t *, _tfinddata *, void *)
MyProgram.exe!EnumMatches(const std::basic_string<wchar_t,std::char_traits<wchar_t>,std::allocator<wchar_t> > &, const std::vector<std::basic_string<wchar_t,std::char_traits<wchar_t>,std::allocator<wchar_t> >,std::allocator<std::basic_string<wchar_t,std::char_traits<wchar_t>,std::allocator<wchar_t> > > > &, int (const wchar_t *, _tfinddata *, void *)*, void *, int)
...

Так что совершенно очевидно, что копирование std::string занимает слишком много времени, возможно, из-за плохой привязки.

Так что теперь мой вопрос прост:

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

Answer 1

Одним из способов было бы прекратить помещать их по значению в структуру SearchSuggestion. Вместо этого дайте каждому SearchSuggestion указатель на std::string, который представляет путь.

struct SearchSuggestion {
  int pathId;
  int tag;
};

Это сделает копирование внутри вектора более эффективным, так как оно будет копировать только простые int s вместо сложных std::string значений.

Затем вы можете использовать структуру std::map<int, std::string>, чтобы отобразить идентификаторы пути в реальные пути.

Answer 2

Вы можете попробовать использовать Boost.Flyweight. Я не гарантирую, что это сработает & mdash; время, сэкономленное от не копирования строки, может быть потрачено на проверку того, не была ли эта строка еще сохранена & mdash; но вы можете попробовать.

Другой вариант - превратить его в boost::shared_ptr<std::string>. Теперь есть только указатель, который нужно будет скопировать (поэтому стоимость будет практически нулевой), но теперь есть дополнительная стоимость при фактическом доступе к этой строке (но это может быть не такой большой проблемой).

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

Answer 3

Попробуй форс :: мухи:

http://www.boost.org/doc/libs/1_40_0/libs/flyweight/doc/tutorial/basics.html

Answer 4

Самый лучший ответ: не выделяйте и не копируйте много строк. Вместо этого используйте общие указатели на постоянные строки или символы.

Malloc () и strcpy () просто медленные, точка, и копирование строки всегда будет операцией O (n). В коде реального времени лучше просто избегать выделений как можно больше.