Sign in to follow this  
herc

Unity stack based string class

Recommended Posts

my post should be rather added to this thread Memory Allocator for string class but its retired. (admin: maybe reopen it and add my following as a reply) ------- if you have many small string, that serve just the purpose to deliver some short messages and stuff, and do NOT need to be concatenated till whatever length, i would suggest to just use the stack. why must all stuff be on the heap? so i propose to supply a stack based "clone" of std::string. with a fixed size, simple c-array of some char type. would this work? or is there any issues then with thread and whatever else safety one could run into? i have , for example, implemented my own small stack based vector class. vector_stack_allocated.hpp it is based on the fine boost::array ( http://www.josuttis.com/cppcode, http://www.boost.org/doc/html/boost/array.html ). and i am using it without any troubles in my small game project ( www.gravytris.de ). so, would this be possible with strings too? and if so, is there eventually already such a stack based, STL compatible string class implemented somewhere?

Share this post


Link to post
Share on other sites
Instead of writing stack-based vectors, strings and the likes, the STL has the concept of an allocator.

Write a 'stack-based allocator' and pass your custom allocator to a vector class or to a string (basic_string) and then when the container wants to allocate memory it gets given pointers to the stack instead of the heap; the container itself doesnt even know.

The boost::array is in-fact a complete re-write of a vector using the stack, but it does this purely for raw efficiency, as a trade-off it's not fully STL compliant and it'll only ever be a static-array.
The beauty of using allocators is that you can pass your allocator to all of the STL types, so you can have stack-based lists or maps too. The containers don't need to change.

You might not be aware of this, but the STL forces no requirements on how a string is implemented, a std::string implementation is likely to use a combination of stack-based and heap-based allocations.

Please be aware that writing stack-based alternatives is really only any use if you know that dynamic allocation is too slow.

Share this post


Link to post
Share on other sites
i am aware of ALL your points, i know that it MIGHT be that lists and strings use a pool-allocator, depending on implementation. in fact, at least for lists, i somewhere have read that microsoft stl implementation does use pool allocation.

i also know that you might supply a stack based allocator, but i know/suspect too that it is utterly difficult to write an allocator, instead of a rather simple, tiny stack based string / vector (that of course is then only partially compatible to STL).

but then - do you know any stack based allocator, ready to use ? that could be passed to std::string ?

Share this post


Link to post
Share on other sites
Quote:
i also know that you might supply a stack based allocator, but i know/suspect too that it is utterly difficult to write an allocator, instead of a rather simple, tiny stack based string / vector (that of course is then only partially compatible to STL).

Writing an allocator isn't that hard, you could argue its actually the easier option.
For an allocator you just have to implement some functions for basic memory management (which in the case of stack-allocator would be trivial), if you wrote your own container without allocators then you'd still need to code up the memory management but also all the other functions that go with the container.

Allocators 'seem' mysterious to the uninitiated, but they're not so bad:

Tutorial on writing allocators

Presentation on custom allocators

Quote:
do you know any stack based allocator, ready to use ? that could be passed to std::string ?

No, sorry.
Google might hold the answer though.

Share this post


Link to post
Share on other sites
Quote:
i also know that you might supply a stack based allocator, but i know/suspect too that it is utterly difficult to write an allocator, instead of a rather simple, tiny stack based string / vector (that of course is then only partially compatible to STL).


Let's see.

Writing an allocator (a mechanism, designed to be supplied by user in extensible fashion) vs. writing a complete string class (fully STL compliant, with all the hundreds of functions, fully templated to be compliant with STL container requirements).

Which is more viable?

Writing an allocator is tricky. But it's a 5 minute task compared to re-implementing all thousands of lines of code and several implementation files that comprise a std::basic_string<T>.

The choice should be obvious (PPT)

Share this post


Link to post
Share on other sites
1) Many implementations of std::string are optimized for the case of short strings, by adding a small char[] buffer to the data struct and using that when the string will fit.

2) If you really, definitely aren't going to perform any mutating operations, and you're really paranoid about overhead, you might as well just use string literals (horrors! [wink]). If you're not trying to change the data, then the only way you can really mess up is by disregarding what strlen() (or std::find() looking for a '\0', if you want to be bizarrely modern) tells you. (Of course, const correctness is your friend.) Unless you require strings with embedded '\0' characters, I guess.

Share this post


Link to post
Share on other sites
for std::string, you people are completely right. that string class is so much more complex regarding the interface than the simple vector class. i would say that my stack based vector implementation is simpler than a custom memory allocator. by the way - do you have any comments on how i did my stack vector class? any obvious pitfalls visible by just inspecting the code?

here it is again, in syntax highlighted html:
vector_stack_allocated_hpp.html

but one can only really tell by trying. thanks for the links, i will try to fight my way through that "write my own mem alloc" stuff.


Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
1) Many implementations of std::string are optimized for the case of short strings, by adding a small char[] buffer to the data struct and using that when the string will fit.


interesting! i will check that with my debugger. ir do you know if it is the case for visual studio 8 ?

Share this post


Link to post
Share on other sites
Quote:
Original post by dmatter
You might not be aware of this, but the STL forces no requirements on how a string is implemented, a std::string implementation is likely to use a combination of stack-based and heap-based allocations.

Quote:
Original post by herc
Quote:
Original post by Zahlman
1) Many implementations of std::string are optimized for the case of short strings, by adding a small char[] buffer to the data struct and using that when the string will fit.


interesting! i will check that with my debugger. ir do you know if it is the case for visual studio 8 ?

Yes, a stack buffer between 1 and 16 elements depending on the size of 1 element (typically a char type). Its defined by the size of _BUF_SIZE.

Share this post


Link to post
Share on other sites
Quote:
Original post by herc
any obvious pitfalls visible by just inspecting the code?

I glanced over it, it looks ok.
One issue to keep in mind is that because its a stack-based array when you call erase on an element it isnt actually destructed. If you had it storing objects that were very sensitive to when they're destroyed this might cause unforseen complications, but that's not a problem with your code that's just what happens with the stack anyway.

Quote:
thanks, this is great news! most of my small strings are never longer than 16 chars.

Good for you [smile]

This is why trying to second-guess the STL is usually a waste of time, its highly optimised in the first place. Just imagine if you'd spent all that time coding up a stack based string class when all you ever do is use it for 10-char strings [wink].

Share this post


Link to post
Share on other sites
Quote:
Original post by herc
for std::string, you people are completely right. that string class is so much more complex regarding the interface than the simple vector class. i would say that my stack based vector implementation is simpler than a custom memory allocator. by the way - do you have any comments on how i did my stack vector class? any obvious pitfalls visible by just inspecting the code?


I have the following comments.

(1) This is almost identical to the standard container designed to do exactly the same job (tr1::array, or std::array in C++09). Not surprising: it's filling the same need.

(2) One of the guidelines following in designing the standard containers was that functionality that could onlt be imeplemented poorly should not be implemented at all. Some of the functions you've carried across from std::vector can not be implemented properly in a stack-based vectorlike container. For example, resize(), reserve(), and swap(). This is why the standards committee came up with std::array: a different name for a different set of requirements and functionality.

--smw

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

  • Partner Spotlight

  • Forum Statistics

    • Total Topics
      627653
    • Total Posts
      2978433
  • Similar Content

    • By STRATUM the Game
      Hey, everyone! This is my first post here.
      I would like to know what you think about my project called STRATUM. It's a 2D platformer that is heavily based on storytelling and boss fighting while trekking through the world.

      Everything in STRATUM takes place in the first century AD, in a world that wraps our own universe, called  The Stratum. A parallel Universe that is the home of the Christian deities . In this game you will play as a Dacian warrior, unfamiliar with everything in this world, you’ll get to know and understand The Stratum together with him.
      The main thing that I want with STRATUM is to reinvent the known lore and history of the Christian deities and realms. 
      The story is unconventional, it plays down a lot of the mysticism of Hell or Heaven and it gives it a more rational view while keeping the fantastic in it. What do I mean by that? Well, think about Hell. What do you know about it? It's a bad place where bad people go, right? Well, that's not the case in STRATUM. I don't want to describe such a world. In STRATUM, there is a reason for everything, especially for the way Hell is what it is in the game. "Hell" is called The Black Stratum in the game.
      This world is not very different from Earth, but it is governed by different natural laws.
      The story will also involve the reason why this world entered in touch with ours.

       
      What do you think about all that I said? Would you be interested in such a game? I have to say that everything is just a work of fiction made with my imagination. I do not want to offend anyone's beliefs.
      I want this to be a one man game. I have been working alone on it (this was my decision from the beginning) from art to effects to programming to music to sound effects to everything.
      I also have a youtube video HERE if you want to see the way the game moves and the way my music sounds.
      Please, any kind of feedback will be highly appreciated. If you have something bad to say, do it, don't keep it for yourself only. I want to hear anything that you don't like about my project.
       
    • By LimeJuice
      Hi, it's my first post on this forum and I would like to share the game I am working on at the moment.
      Graphics have been made with Blender3D using Cycle as a renderer and I am using Unity3D. It's a 2D game, one touch side-scrolling game for iOS and Android.
      Here some pictures, and you can have a look to the gameplay on this video :
      Feedbacks ?
      And if you want to try it, send me your email and I will add you to the beta tester list!
       
       








    • By Kirill Kot
      An adventure indie game with quests in a beautiful, bright world. Characters with unique traits, goals, and benefits. Active gameplay will appeal to players found of interactivity, especially lovers of quests and investigations.
      Available on:
      Gameroom (just open the web page and relax)
      AppStore
      GooglePlay
      WindowsPhone

    • By Kirill Kot
      Big Quest: Bequest. An adventure indie game with quests in a beautiful, bright world. Characters with unique traits, goals, and benefits.
      Mobile game, now available on Gameroom. Just open the web page and relax.
    • By Kirill Kot
      Big Quest: Bequest. An adventure indie game with quests in a beautiful, bright world. Characters with unique traits, goals, and benefits.
      Mobile game, now available on Gameroom. Just open the web page and relax.
  • Popular Now