View Issue Details

IDProjectCategoryView StatusLast Update
0002644FSSCPPlatform-Engine interactionpublic2012-05-02 15:19
ReporterEchelon9 Assigned ToEchelon9  
PrioritynormalSeveritymajorReproducibilityalways
Status resolvedResolutionfixed 
Product Version3.6.14 
Target Version3.6.14 
Summary0002644: Replace vector<bool> with proper STL deque<bool>
DescriptionSTL vector<bool> is neither a vector, nor does it contain true bools.

This is a gotcha of the STL, which the standards body attempted to optimize early by replace vector<bool> with a pseudo-STL type.

The internal representation aren't bools, but bits. This has a sight memory improvement, but means normal STL operators and assumptions do no hold for this container type.

In the interests of not getting caught out by this issue later on, I'm replacing with deque<bool>, which is a proper STL container type of bools.

cf:
http://www.gotw.ca/publications/mill09.htm and
Effective STL by Scott Meyers, Item 18 : Avoid using vector<bool>
TagsNo tags attached.

Activities

Echelon9

2012-04-29 02:52

developer  

stl-vector-bools-fix-v1.diff (993 bytes)   
Index: code/menuui/mainhallmenu.cpp
===================================================================
--- code/menuui/mainhallmenu.cpp	(revision 8690)
+++ code/menuui/mainhallmenu.cpp	(working copy)
@@ -1102,11 +1102,15 @@
 	}
 }
 
-// render all playing misc animations
+/**
+ * Render all playing misc animations
+ *
+ * @param frametime Animation time
+ */
 void main_hall_render_misc_anims(float frametime)
 {
 	int idx, s_idx, jdx;
-	SCP_vector<bool> group_anims_weve_checked;
+    std::deque<bool> group_anims_weve_checked;
 
 	// render all misc animations
 	for (idx = 0; idx < Main_hall->num_misc_animations; idx++) {
Index: code/ship/ship.h
===================================================================
--- code/ship/ship.h	(revision 8690)
+++ code/ship/ship.h	(working copy)
@@ -727,7 +727,7 @@
 	int ab_count;
 
 	// glow points
-	SCP_vector<bool> glow_point_bank_active;
+    std::deque<bool> glow_point_bank_active;
 
 	//Animated Shader effects
 	int shader_effect_num;

iss_mneur

2012-04-29 03:46

developer   ~0013485

The reasoning makes sense to me. Though, I don't think we use vector<bool> in anyway that violates its more restricted semantics.

I am also wondering about the penalties from accessing a linked list (which is what a deque is implemented as, IIRC). The reason that I ask, is I know that the vector<bool> in the mainhall code is accessed with indexes and not by iterators. I am also pretty sure that the other one gets accessed via indexes as well.

Admittedly both of these instances have a low value of n (usually about 5 IIRC), so its probably not really an issue. But I am left wondering, is the problem described in the linked article actually being seen by FSO code?

Echelon9

2012-04-29 03:57

developer   ~0013486

Last edited: 2012-04-29 03:58

I'm not convinced that we see any of the problems in the way the FSO code uses vector<bool> currently.

However, there's a slight difference in that the examples of vector<bool> use the vector.at(index_num) rather than a vector[index_num] accessor approach. We use .at() accessor method rarely elsewhere within the code, due to the extra overhead it requires.

Without knowing the reasons why mainhallmenu was written this way, it may have been because the vector[index_num] method violates some the linked article's concerns.

In any case, I think we should be extra careful using vector<bool> anywhere, as we all know how often FSO code has copy/pasted sections when implementing a new piece of logic. I don't want to see the vector<bool> approach used elsewhere in a manner that may trip up.

iss_mneur

2012-04-29 04:31

developer   ~0013487

CommanderDJ was the coder that added this code that uses the .at(). He should be able to provide more insight as to why he chose to do it that way.

Also, see this post http://www.hard-light.net/forums/index.php?topic=78856.msg1572481#msg1572481 as mentions a reason for him using it.

iss_mneur

2012-04-29 04:33

developer   ~0013488

Added CommanderDJ to the bug so that he can comment on his use of .at().

CommanderDJ

2012-04-29 04:57

developer   ~0013489

The post Iss linked pretty accurately describes my reasoning for using .at(). The impossibility of unknowingly performing out-of-bounds access when using .at() was my main reason, and in my view the extra overhead is well worth the insurance, because it makes at least that one sort of bug very obvious, and indeed it helped me catch quite a few during my work on the mainhall code, which would have taken longer to track down had I been using [].

My use of .at() with vectors goes back to how I was taught in my first year of uni (college), and I admit we were not introduced very much to iterators so I am unfamiliar with their pros and cons.

All that said, I am still a new SCP member, and if my views differ significantly from other team members then I am happy to adjust code I write to fit with existing conventions.

Is that sufficient clarification?

The_E

2012-05-02 11:13

administrator   ~0013497

If the mainhall code was in any way performance-critical, I'd argue in favour of using the [] operators. As it is, the extra safety from using at() does not come at a significant price in this instance, so I'm certainly okay with it.

Echelon9

2012-05-02 15:19

developer   ~0013510

Fix committed to trunk@8742.

Related Changesets

fs2open: trunk r8742

2012-05-02 11:20

Echelon9


Ported: N/A

Details Diff
Fix Mantis 2644: Replace vector<bool> with proper STL deque<bool>, thanks IssMneur and CommanderDJ Affected Issues
0002644
mod - /trunk/fs2_open/code/ship/ship.h Diff File
mod - /trunk/fs2_open/code/menuui/mainhallmenu.cpp Diff File

Issue History

Date Modified Username Field Change
2012-04-29 02:52 Echelon9 New Issue
2012-04-29 02:52 Echelon9 Status new => assigned
2012-04-29 02:52 Echelon9 Assigned To => Echelon9
2012-04-29 02:52 Echelon9 File Added: stl-vector-bools-fix-v1.diff
2012-04-29 02:52 Echelon9 Status assigned => code review
2012-04-29 03:23 iss_mneur Description Updated
2012-04-29 03:46 iss_mneur Note Added: 0013485
2012-04-29 03:57 Echelon9 Note Added: 0013486
2012-04-29 03:58 Echelon9 Note Edited: 0013486
2012-04-29 04:31 iss_mneur Note Added: 0013487
2012-04-29 04:33 iss_mneur Note Added: 0013488
2012-04-29 04:57 CommanderDJ Note Added: 0013489
2012-05-02 11:13 The_E Note Added: 0013497
2012-05-02 15:19 Echelon9 Changeset attached => fs2open trunk r8742
2012-05-02 15:19 Echelon9 Note Added: 0013510
2012-05-02 15:19 Echelon9 Status code review => resolved
2012-05-02 15:19 Echelon9 Resolution open => fixed