Loading...
MartinBG avatar MartinBG 4803 Точки

[Texts and Colors] Въпрос за TextContainer и Text

1. В предложеното на лекцията решение SDL_Texture* се пазят във vector, чиито индексите са и textId:

class TextContainer {
//...
  void occupyFreeSlotIndex(int32_t &occupiedTextId);
  void freeSlotIndex(int32_t textId);

  //the textures we'll be drawing
  std::vector<SDL_Texture*> _textures;
//...
}

Каква е причнината горното решение да е предпочетено, спрямо решение с unordered_map? Гледах лекцията отново, но явно изпускам нещо.

Например:

class TextContainer {
//..
  int32_t nextTextId{0};
  std::unordered_map<int32_t, SDL_Texture*> _textures;
}

=================

void TextContainer::createText(...)
  //..
  ++nextTextId; //unique id
  if (const auto&[i, success] = _textures.try_emplace(nextTextId, textTexture); success) {
    outTextId = i->first;
  }
  //...
}

 

 

2. Забелязах, че не извикваме gRsrcMgr->unloadText(_drawParams.textId) в Text::destroy() и съответно не се изтриват ненужните текстури, т.е. липсва този код:

  if (gRsrcMgr) {
    gRsrcMgr->unloadText(_drawParams.textId);
  }
Тагове:
1
C++ Applications Development 06/11/2021 05:39:18
j.petrov_90 avatar j.petrov_90 373 Точки

Привет, MartinBG,

Благодаря за включването.
Винаги ми става приятно като се получи дискусия /аз също се уча доста от Вас, за което съм благодарен /

Започвам с т.2, че е по-кратка:
2. Забелязах, че не извикваме gRsrcMgr->unloadText(_drawParams.textId) в Text::destroy() и съответно не се изтриват ненужните текстури, т.е. липсва този код:

Не мога да кажа на черното - бяло. Прав си.
Хубавата новина,  е че това бързо би го хванал човек, защото би му се напълнил контейнера (няма кой да освобождава текстовете).
Или големината на контейнера щеше да е подозрително голяма, ако винаги го resize-вахме run-time.


1. В предложеното на лекцията решение SDL_Texture* се пазят във vector, чиито индексите са и textId:
Каква е причнината горното решение да е предпочетено, спрямо решение с unordered_map? Гледах лекцията отново, но явно изпускам нещо.


Споделям разсъждения. Ще се радвам, ако и аз пропускам нещо да ме обориш.

Започвам от далече.
Векторът е най-добрата и най-бърза структура в 90% от случаите.
Голяма част от това се дължи на sequental memory layout и съпровождащите ги cache hits, когато се работи със структурата.
Отделно lookup time-а му е чиста O(1) константа - just a pointer hop.

Хештаблицата също "диша във врата" на вектора.
Има амортизирана константна сложност O(1) за lookup.
За жалост, обаче има и скрита цена (не говорим само за big-O complexity).
Първо плащаш хешираща функция. Второ имаш collision resolution, който също не е безплатен.
В зависимост от collision resolution стратегията - имлементацията би използвала свързан списък или би съхранявала ключовете заедно с елементите.
Това води до cache misses or more cache loads. 

Това обаче се микро-оптимизации, които в общия случай не ни интересуват.
Хештаблицата съществува за да решим проблема как от произволни ключове можем да образуваме mapping към array indexes.
Например ок ключове 1, 3, 2048930589, -2432535 в перфектния случай бихме искали да имаме масив от 4 елемента.
Това ни идва на готово от std::unordered_set/map скруктурите.

Това е и казусът при ImageContainer-а.
В него имаме std::unordered_map, защото уникалните ключове идват "отвън".
Да, ние ги създаваме в enum с поредни индекси, но това не е задължително да е вярно.
В реалност тези id-та трябва да бъдат наистина уникални (или близки до уникални).
Взимам нещо, което е уникално като например пътя на всеки файл и хешираш него.
Ето ги уникалните не-последователни TextureIds.

При TextContainer-а обаче, с std::unordered_map искаш да решиш проблем, който не съществува.
Вече си имаш вектор, който "раздава" уникални последователни id-та.
Защо да си разваляш уюта :)

Накрая, но не на последно място - предложението, което си дал, мисля, че няма да издържи на следния случай.
Add (idx 0), add (idx 1), add (idx 2), add (idx 3)
remove (idx 2)

Предполагам, че remove би се имплементирало с директно триене на елемента от хештаблицата.
Ефективно ще имаш handles 0, 1, 3

При следващ request за add кое Id би дал?
За да си намери "дупката" 2 - пак трябва линейно да се обходи целият контейтер.
Помни, че това е std::unordered_map и там нямаме гаранция, че елементите ще бъдат подредени в реда, в който ги insert-нем.

Ако решиш да не го обхождаш:
Или трябва просто да даваш винаги следващото "id". В един момент брояча би overflow-нал. Т.е. пак се връщаме до метода със линейното сканиране.
Или пък, ако винаги ще даваш handle == map.size(), то би имал колизия с предходен елемент под това id.

Поздрави

2
07/11/2021 14:43:14
MartinBG avatar MartinBG 4803 Точки

Благодаря за подробния отговор!

Сигурен съм, че ще е полезен и за други колеги от групата!

 

Изглежда, че съм разбрал правилно идеята, но имплементацията ми се струва ненужно сложна, с потенциал да бъде по-бавна от такава с unordered_map заради occupyFreeSlotIndex, която е с линейна сложност, а има и сценарии, при които може да се окажем с ненужно голям вектор, пълен с nullptr, защото не е предвиден вариант за "свиването" му.

Горното в никакъв случай не трябва да се приема като критика, дори напротив, защото не би ми хрумнало да подходя към проблема по този начин и научих нещо ново. :)

 

Наистина, варианта с unordered_map ще има проблем ако nextTextId прелее, мине през всички отрицателни стойности и стигне отново до 0, но това са над 4 милиарда id-та и ако приложението не се очаква да генерира подобно количество стрингове за една сесия, мисля че логване на грешка при превъртане (т.е. nextTextId < 0) е достатъчна "защита".

 

 

2
07/11/2021 23:30:01
j.petrov_90 avatar j.petrov_90 373 Точки

Получи се добра дискусия :)

В заключение ще кажа, че и двата варианта са добри. Всеки си има trade-offs.

В зависимост от нуждите на приложението си човек може да прави всякакви оптимизации.
Ако ще има rapid text creation и в последствие rapid text destruction би имало логика да се имплементира shrinkToFit функция на варианта с вектор.

Човек, ако се замисли даже може да види, че това е много basic версия на това как ОС-а раздава памет от heap-a :)
А в последствие shrinkToFit би било дефрагментацията.

Накрая, но не на последно място искам да спомена, че signed integer overflow е undefined behavior.
Нямаш гаранция, че INT32_MAX + 1 == INT32_MIN
Компилаторите си прилагат custom оптимизации върху signed integer overflow.
Но от компилатор до компилатор има разлика.

Единствено unsigned integer overflow е defined.

Поздрави

1
08/11/2021 15:25:20
MartinBG avatar MartinBG 4803 Точки

yes

 

Имплементацията на shrinkToFit функция няма да е лесна задача, защото ще промени индексите на текстурите, а тези индекси се ползват от нашите имиджи, т.е. ще трябва да има обратна референция от индексите на текстурите към всички имиджи, които ги ползват, за да бъдат ъпдейтнати.

 

Не знаех, че signed integer overflow е undefined behavior.

За който му е интресно, ето и дискусия в SO по темата.

 

0
08/11/2021 15:32:15
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.