STL speed question

Started by
45 comments, last by phillip_fletcher 20 years, 11 months ago
quote:Original post by petewood
plenty of articles on eXtreme Programming practices here
there is a pair-programming one in particular


Well, I read through that example and, well... I’ll try to be nice.

First, they really take a long route to get where they are going. The code goes through lots of iterations before it’s done, getting worse before it gets better. This seems to be a result of coding for one test case at a time. They write a program that satisfies the first test case. Then they think up a second test case. Then they realize that what they have can’t work with the second test case and they have to rewrite it. The code goes through many changes that I think are senseless. I don’t think that’s a very good process. Perhaps this example was meant to demonstrate pair programming but not necessarily a good design. However, if this kind of thinking process leads to that kind of design, then I think I would prefer a different process.

The program is not really object-oriented. There’s really only one class, game, and it has all the data and all the code. By making a scorer class at the end, all they’re really doing is grouping procedural code together in its own class. It’s not really object-oriented. There is no “scorer” in the problem domain.

They talked themselves out of a linked list at the beginning because it may not be needed. Well, of course you can avoid using a linked list if you want. You can also use assembly language—Java or C is not really necessary. They didn’t need to use a linked list or use a frame class for this particular program. But in making that choice I think they also abandoned an object-oriented design.

So who cares if it’s object-oriented or not? Well, the reason we make object-oriented code is because it’s a general way to make a program tolerant of future changes when we don’t know what the changes are going to be .

XP doesn’t seem to care about the future as much. You may argue that there’s no sense in writing code that may never be needed. That’s true. But it’s a pretty safe bet that improvements and changes will need to be made in the future. And I think you’re shooting yourself in the foot if you pretend that that’s not going to happen.

I wrote the bowling program in an alternative way, using C++ because I don’t have Java. (And I did use a linked list.)


      #include <iostream>using namespace std; class Frame{ public:	Frame() 		:m_pPrevious(NULL),		m_pNext(NULL),		m_firstThrow(0),		m_secondThrow(0),		m_nextThrow(1)	{}	void SetNext(Frame *pNext) { m_pNext = pNext;}	void SetPrevious(Frame *pPrevious) {m_pPrevious = pPrevious;} 	virtual bool Add(char pins);	virtual int GetScore();	char GetFirstThrow()	{ return m_firstThrow; } private:	virtual char GetTwoThrows(void);	// gets the sum of the score of the next two throws	bool IsStrike()			{ return m_firstThrow >= 10; }	bool IsSpare()			{ return (m_firstThrow + m_secondThrow) >= 10; } protected:	Frame			*m_pNext;	Frame			*m_pPrevious;	char			m_firstThrow;	char			m_secondThrow;	unsigned char	m_nextThrow;	// starting at one, the next throw to be made for this frame; };// Return the sum of the next two throws.// If this frame is a strike, it will in turn need to query the following frame for it's first throw// in order to sum two throws.char Frame::GetTwoThrows(){	if(IsStrike())		return m_firstThrow + m_pNext->GetFirstThrow();	else		return m_firstThrow + m_secondThrow;} int Frame::GetScore(){	int score = m_firstThrow + m_secondThrow; 	// Accumulate score from previous frames	if(m_pPrevious)		score += m_pPrevious->GetScore(); 	if(m_pNext)	{		// Account for a strike		if(IsStrike())			score += m_pNext->GetTwoThrows(); 		// Account for a spare		else if(IsSpare())			score += m_pNext->GetFirstThrow();	} 	return score;} // Add pins to this frame.// Return true if more throws can be added to this frame,// return false if this frame is done;bool Frame::Add(char pins){	switch(m_nextThrow)	{		case 1:			m_firstThrow = pins;			m_nextThrow += (pins >= 10) ? 2 : 1;			break;					case 2:			m_secondThrow = pins;				m_nextThrow++;			break;	}; 	// return false if this frame is done	if(m_nextThrow > 2)		return false;	 		return true;} class LastFrame : public Frame{public:	LastFrame()		: Frame(),		m_thirdThrow(0)	{} 		virtual bool Add(char pins);	virtual int GetScore(); private:	virtual char GetTwoThrows();	char m_thirdThrow;}; char LastFrame::GetTwoThrows(){	return m_firstThrow + m_secondThrow;} int LastFrame::GetScore(){	int score = m_firstThrow + m_secondThrow + m_thirdThrow; 	// Accumulate score from previous frames	if(m_pPrevious)		score += m_pPrevious->GetScore(); 	return score;} bool LastFrame::Add(char pins){	switch(m_nextThrow)	{		case 1:			m_firstThrow = pins;			m_nextThrow++;			break;					case 2:			m_secondThrow = pins;				m_nextThrow++;			break;		case 3:			m_thirdThrow = pins;				m_nextThrow++;			break;	};	// return false if this frame is done	if(m_nextThrow > 3)		return false;	 		return true;} class Game{	enum {NUMFRAMES = 10};	Frame *Frames[NUMFRAMES];public:	Game();	~Game();	void Add(char pins);	int GetScore()		{	return GetScoreFrame(m_currentFrame);	}	int GetScoreFrame(int frame)		// first frame is frame 1. there is no frame 0.	{	return Frames[frame - 1]->GetScore();	}	int GetCurrentFrame()	{	return m_currentFrame;	}private:	int m_currentFrame;}; void Game::Add(char pins){	if((Frames[m_currentFrame - 1]->Add(pins) == false) && (m_currentFrame < 10))		++m_currentFrame;} Game::Game()	:m_currentFrame(1){	// Allocate Frames	for(int i = 0; i < NUMFRAMES - 1; i++)		Frames[i] = new Frame;	Frames[NUMFRAMES - 1] = new LastFrame; 	// Setup Previous pointers	Frames[0]->SetPrevious(NULL);	for(int i = 1; i < NUMFRAMES; i++)		Frames[i]->SetPrevious(Frames[i-1]); 	// Setup Next pointers	for(int i = 0; i < NUMFRAMES - 1; i++)		Frames[i]->SetNext(Frames[i+1]);	Frames[NUMFRAMES - 1]->SetNext(NULL);} Game::~Game(){	// deallocate the frames	for(int i = 0; i < NUMFRAMES; i++)	{		if(Frames[i])			delete Frames[i];		Frames[i] = NULL;	}} int main(){ 	Game game; 	// Run a sample game	for (int i=0; i<9; i++)		game.Add(10);	game.Add(9);	game.Add(1);	game.Add(1);  	cout << " Frame: " << game.GetCurrentFrame() << endl;	cout << " Score: " << game.GetScore() << endl; 	char keypress;	cin >> keypress;	return 0;}      


This version uses a Frame class. Derived from that is a special case frame, the LastFrame (the tenth frame). This frame has different behavior. It’s not perfect and you could probably improve it. But it’s just to illustrate a point.

The disadvantages of this version are that it takes a bit more memory due to the link pointers and the extra m_nextThrow variable I used. Also, it looks like it’s a little longer just in terms of lines. You could use an STL linked list to make it easier and a little shorter, but I didn’t want to use STL for an example.

I believe there are a couple of advantages to this version. First, to me anyway, this is clearer and more easily understood. But I suppose everyone thinks their own code is easier to understand than that of other people, so I won’t be the judge of that.

I also think it is more tolerant of future changes. Let’s say you want to add a feature that let’s you rearrange the frames in a different order to see if you would have gotten a higher score if you bowled in a more “serendipitous” order. This is not hard because you can just rearrange the order of the linked list. In the Java version it is harder because there is no real concept of where frames start and end unless you are sequencing through the list. What if you want to add a function that tells you how many pins you got down in any one frame? Which program would you rather add this functionality to? What if you want to invent a new type of bowling frame that scores differently or has four throws?

In that example, they were able to bank on the fact that the game of bowling doesn’t change. It always has ten frames and it’s always scored the same. But in the real world, most of the things you model will change.

Maybe I’m harping on their design too much and not focusing on the process, which may be the point of the article. But I don’t see how that process is very good; they went through a ton of changes in making a simple program. The alternative program I was able to write straight away. Test-first programming? It seems like what the test-first philosophy is doing for them is causing them to design by contract, which is good. So why not just design by contract?

[edited by - JimH on May 7, 2003 11:25:20 PM]
Advertisement
quote:Original post by JimH
First, they really take a long route to get where they are going. The code goes through lots of iterations before it’s done, getting worse before it gets better.

But in other systems, you often have lots of iterations on paper in order to reduce the number of code iterations. So you''re just moving the iterations. As a programmer, I often find it easier to do this in code. I''m used to changing code, refactoring things, and so on... this comes just as quickly and more naturally to me than redrawing yet another UML diagram.

quote:The program is not really object-oriented. There’s really only one class, game, and it has all the data and all the code. By making a scorer class at the end, all they’re really doing is grouping procedural code together in its own class. It’s not really object-oriented. There is no “scorer” in the problem domain.

Doesn''t matter. Object-orientation is a means, not an end. The end is ''working, tested, feature-complete software'', and their method tests it robustly and delivers a working product that looks maintainable (to me).

quote:So who cares if it’s object-oriented or not? Well, the reason we make object-oriented code is because it’s a general way to make a program tolerant of future changes when we don’t know what the changes are going to be .

But so is structured programming. And any other number of paradigms. The people in the article used OOP, just not in the way that you might. Partly this is because they believe in refactoring, which is another way of accommodating those changes.

quote:They talked themselves out of a linked list at the beginning because it may not be needed. Well, of course you can avoid using a linked list if you want. You can also use assembly language—Java or C is not really necessary.

That''s a poor comparison: a linked list is frequently more complex than the alternative. Whereas using C++ instead of assembly is going to be less complex. Their motivation is to not try to anticipate every possible occurence in advance, as it leads to over-complex designs. Instead, start with the simplest thing that works, prove that it works, and build from there. Perhaps it does take longer, and perhaps you do duplicate a little effort, but you''re always building from a working base. It''s reliability-led, not features-led. (See also: much open-source software vs. Microsoft software.)

quote:In that example, they were able to bank on the fact that the game of bowling doesn’t change. It always has ten frames and it’s always scored the same. But in the real world, most of the things you model will change.

There''s a simple trade-off; you add complexity to gain flexibility. The XP method puts the flexibility into the process rather than the code. It says "your code will change, so learn how to deal with that" rather than "the requirements will change, so try to code for every eventuality".

[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]
quote:Original post by JimH
First, they really take a long route to get where they are going. The code goes through lots of iterations before it’s done, getting worse before it gets better.

Yes, that''s what happens in real life too, whether you pair program or not.
quote:
They talked themselves out of a linked list at the beginning because it may not be needed. Well, of course you can avoid using a linked list if you want. You can also use assembly language—Java or C is not really necessary.

That''s not the point. The point is that the linked-list solution adds speculative generality into the program, which both takes effort and makes the program more complicated. If it turns out that the linked-list isn''t needed after all, then the effort has been wasted and the program is over-complex.
quote:
So who cares if it’s object-oriented or not? Well, the reason we make object-oriented code is because it’s a general way to make a program tolerant of future changes when we don’t know what the changes are going to be .

OO cannot guarantee that, since it does not help you predict the future. There''s no particular reason an OO program should be easier to change than a procedural one - that''s just OO marketing spin. One thing that does make your code easier to change is having a good suite of tests which tell you when things break as changes are applied.
quote:
XP doesn’t seem to care about the future as much.

You''re badly missing the point of XP. XP is exactly about writing software which is easy to evolve. It''s about making sure you don''t add wasteful speculative generality, which makes s/w harder to change. It''s about making sure you have unit tests, which are both a measure of correctness and a safeguard against erroneous changes. It''s about discovering what is needed in the face of uncertainty. And it''s about writing exactly what is needed to solve a problem.
quote:
You may argue that there’s no sense in writing code that may never be needed. That’s true. But it’s a pretty safe bet that improvements and changes will need to be made in the future.

So make them. Speculative generality won''t help in that, because you will more often than not have speculated wrong. It may even make it harder, because you have all these devices and levels of indirection sitting around which you *have to* comprehend before being confident of what change you need to make.
quote:
I also think it is more tolerant of future changes. Let’s say you want to add a feature that let’s you rearrange the frames in a different order to see if you would have gotten a higher score if you bowled in a more “serendipitous” order.

You''re coming up with convenient arguments to make your code seem superior. What if it never changes in the way you suggest? Then you''ve wasted your time adding in `future-proofing''. If it does change in the way you suggest, then just apply the required changes. What''s the problem? It doesn''t cost more to do because your tests tell you that bugs haven''t been introduced. Speculative generality, IME, is a huge cause of s/w being late or even failing to deliver.
quote:
Maybe I’m harping on their design too much and not focusing on the process, which may be the point of the article.

Yes it is. The point has been lost on you.
quote:
But I don’t see how that process is very good; they went through a ton of changes in making a simple program.

Right. So do you when you write s/w, unless you only ever write things that have been written so many times before that you know them line-for-line, in which case you''re wasting your time anyway.
quote:
The alternative program I was able to write straight away. Test-first programming? It seems like what the test-first philosophy is doing for them is causing them to design by contract, which is good. So why not just design by contract?

Because design by contract doesn''t separate the concerns.
quote:JimH
In that example, they were able to bank on the fact that the game of bowling doesn’t change. It always has ten frames and it’s always scored the same. But in the real world, most of the things you model will change.


You were doing really well up until this point:

''Most of the things you model will change''.
Not true. Not false. Who knows?

Generalities are almost always unhelpful.

Anyway, aside from that, the code they end up with is thoroughly tested and if they start making the changes you suggest (ie the requirements change) they are in a good position to start. They have a method to be able to make the changes. One problem I have found with software design is ''analysis paralysis''. I want to know exactly what I''m going to do before I start. But I end up dithering about. I get stuck being unproductive. The bowling score example highlights development. If the requirements change for this or anything you work on then you''ll have to deal with it. This methodology lets you deal with anything that is thrown at you in a consistent way. You just start writing tests and making them pass. What if you had inherited the code in the example (without the tests) and had been asked to make it incorporate the improvements you mentioned, such as a Serendipity Monitor? Where would you start?

1) You might just say "I''ll start again from scratch. I don''t like the code". Then you''d have to re-test the base requirements as well as the new ones (you do test don''t you?). You''ll have a period when nothing compiles or works. You might write the tests when you''ve ''finished'' to show that your code works.

2) You might say "I''ll write a function that starts by using the current storage method and calculates the Serendipity score from there. The function will be ugly as it struggles with the array of scores. Once it''s done and tested I''ll start refactoring and moving towards a more adaptable storage system. All the while my tests will pass''

3) Somewhere else.

Solution (1) is possible in this case but this is a very small example. What about with a 5000 lines-of-code module that already works (give or take a handful of bugs) but is inflexible and needs extending (I could give you one I''ve got sitting right here at work on my harddrive). Even if rewriting meant fewer lines of code (which isn''t guaranteed), you''d have to be a bit crazy to scrub out a whole module even though it''s only 5000 lines of code. If there are tests in place already (not necessarily unit tests), it makes sense to start there.

Finally, the code you''ve written in C++ is written with the hindsight of following through the development of the exact same software in java. You seem to be focusing on the solution in your arguments rather than the process.

I''m really enjoying this discussion and I hope it doesn''t degrade into name calling.

Pete
quote:Original post by petewood
I''m really enjoying this discussion and I hope it doesn''t degrade into name calling.

The original author of this thread is sighing deeply right now

That aside though, I agree that it''s an interesting discussion, and I have no firm opinion either way... each side makes valid points, and I wonder if there might be a middle ground. As far as I can tell, XP and more traditional programming, or rather DESIGN methodologies are not mututally exclusive (correct me if I''m wrong?).

If you peel back some of the jargon introduced with XP (introducing new jargon is a definite point against any new methodology in my books ), it really is rooted in a lot of the same principals that are taught in a more traditional approach to programming. For example, the concept of "refactoring" (who came up with this word??) really is just another way of speaking of abstraction within an OO design... by making your classes have a predefined interface, and even better, but making abstract base classes, and by encapsulating the implementation INSIDE the object, you are free to change the actual code at any time, as long as the interface remains unchanged.

Unit testing is nothing new to anyone in the industry, and although XP uses it rather heavily, it is by no means an exclusive XP construct... in fact, it''s just something that anyone with experience in debugging large projects will inevitably do!

Pair programming I''m a little more sketchy on. Some of the points for and especially against are very true and let me add another. Maybe this is just my small section of the world (although I severely doubt it), but I''ve met many more programmers who lack all social skills, have a pronounced arrogance and are generally not fun people to interact with than otherwise. I know that this isn''t the right place to be making fun of the industry (especially the one that I''m a part of!) but this has been my experience. My point is that there are some definite psycological and social barriers to overcome in pair programming that in many cases would be quite destructive to the whole process. Of course, you can''t see these in the article, since those two naturally get along just fine

If you don''t believe me, just check out the series of "programmers are gods" threads... *sigh*.

Anyways just my 2 cents... like I said, I really have no firm opinion yet though, so keep conversing so I can develop one.
quote:Original post by AndyTX
For example, the concept of "refactoring" (who came up with this word??) really is just another way of speaking of abstraction within an OO design... by making your classes have a predefined interface, and even better, but making abstract base classes, and by encapsulating the implementation INSIDE the object, you are free to change the actual code at any time, as long as the interface remains unchanged.

No, that's not what Refactoring is about. Refactoring is supposed to be an ongoing activity in any software development - there should even be a percentage of development budget set aside solely for improving the internal design of code to delay entropy. A refactoring is a purely structural change to the source, which should not affect the functioning of the code. That means you must have unit tests in place that provide adequate feedback to ensure functionality is not affected. The basic underpinning of when to refactor is the Once and Only Once rule. That is, you shouldn't be duplicating logic around the project. Refactoring adherents suggest that if the same logic exists in two places, it is just about acceptable, but if its in three places, you must refactor.

Anyone who's observed the effect of change on large projects over several years will recognise the software entropy phenonemon, so should be able to appreciate the need to continually refactor in tandem with applying functional changes. Many programmers already do this as a matter of course, but Refactoring aims for a semi-formalised approach.
quote:
Unit testing is nothing new to anyone in the industry, and although XP uses it rather heavily, it is by no means an exclusive XP construct...

XP doesn't claim anything new, its just a conglomeration of existing techniques packaged as a `light methodology'.
quote:
in fact, it's just something that anyone with experience in debugging large projects will inevitably do!

Test-driven design is probably a little more novel to most people than the general idea of unit tests.

Generally, the idea of any methodology is that you take the bits you think are good and you tailor them in a way that helps you to write reliable software. A methodology is not there for you to slavishly adhere to, expecting the software to drop out the end of the process. If anything gets in the way of developing reliable software, then you move it out of the way (it *should* be the role of a manager to remove obstacles from the path of the development team). Always remember that it's about people, not process. Some organisations simply do not have the people or the culture to make something like XP work.


[edited by - SabreMan on May 9, 2003 5:33:41 AM]
Well those are valid points, and under that context, I see no problem with XP, as long as it isn''t regarded as a fundimental change in program design, or people get on power trips over who adheres more strictly to XP etc. Those are my only negative feelings about it really, and they by no means HAVE to happen... I hope they don''t!

This topic is closed to new replies.

Advertisement