Jump to content
  • Advertisement
_WeirdCat_

C++ Dynamic/static allocation of an array c11

Recommended Posts

7 hours ago, Zipster said:

That's besides the point. You can't detect how much stack space is remaining, nor can you even attempt an allocation without overflowing should there be insufficient space. Essentially, your application may or may not crash depending on conditions you can't detect, and there's nothing you can do about it. This is the type of code that should be rooted out, not endorsed.

I don't see why a program must conform the lowest stack size on every compiler.  This use case is not the only one where the stack may overflow.  It's often a problem with recursion and sometimes putting data in the heap can cause a large performance hit in such cases.  To me it's silly. It like saying "you should never increase the default stack size ..... well .... just because". 

I don't think we are going to come to an agreement here so I think I'll just leave it at that.

Share this post


Link to post
Share on other sites
Advertisement

It possible to tweak stack size into linker settings. But  usually it is no sence to do it, becouse a lifetime of big buffers usually much longer than any function length, аnd passing/returning its buffer thru the stack is very expensive. So usually heap or static (data segment)allocation used for buffers intended for similar purposes

Share this post


Link to post
Share on other sites

Ill ask another question, bit off topic but still important, when creating floodfill algorithm which is done by calling recursive function

vec3 color;
void FloodFill(int x, int y)
  {
  color = getpxcolor(x,y);
 FillNext(x+1,y);
  FillNext(x,y+1);
  FillNext(x,y-1);
  FillNext(x-1,y);
  }
void FillNext(int x, int y)
  {
  if (alreadyfilled) return;
  if (getpxcolor(x,y) == color)
    {
  FillNext(x+1,y);
  FillNext(x,y+1);
  FillNext(x,y-1);
  FillNext(x-1,y);
    }
  }

Now i dont remember did this went onto stack, but the question is how to implement this thing that i would not run out of memory (without increasing stack size) for at least 320x240 px image?

Share this post


Link to post
Share on other sites

Don't use a recursive function for floodfill.  Do something like this instead:

          std::vector<vector<int, 2> > points;
          points.push_back(pos);
          while (!points.empty()) {
            vector<int, 2> p = points.back();
            points.pop_back();
            if (pixels[p] == color) {
              pixels[p] = new_color;
              points.push_back(p + vec(0, -1));
              points.push_back(p + vec(0, 1));
              points.push_back(p + vec(-1, 0));
              points.push_back(p + vec(1, 0));
            }
          }

 

Share this post


Link to post
Share on other sites
4 hours ago, a light breeze said:

Don't use a recursive function for floodfill.  Do something like this instead:


          std::vector<vector<int, 2> > points;
          points.push_back(pos);
          while (!points.empty()) {
            vector<int, 2> p = points.back();
            points.pop_back();
            if (pixels[p] == color) {
              pixels[p] = new_color;
              points.push_back(p + vec(0, -1));
              points.push_back(p + vec(0, 1));
              points.push_back(p + vec(-1, 0));
              points.push_back(p + vec(1, 0));
            }
          }

 

If you use a set<> rather than a vector<> as outer container, you'll avoid storing duplicate points, at the cost of defining an ordering function on the 2d vector.

Share this post


Link to post
Share on other sites
1 hour ago, Alberth said:

If you use a set<> rather than a vector<> as outer container, you'll avoid storing duplicate points, at the cost of defining an ordering function on the 2d vector.

...and at the cost of turning O(n) performance into O(n log n).

Share this post


Link to post
Share on other sites

Another way of doing this is from you initial point, to walk forwards in the X direction and then backwards in the X direction and fill with your new color until you get to the boundary on either end.  At the same time you check above and below the line you are on and queue the first point you find for the processing on subsequent iterations. You also need a couple of flags (for above and below) so if you pass a boundary (above or below) you reset that flag so the next open pixel is also queued. This is for going around concave shapes in the vertical direction

Then you un-queue your first point and repeat until there are no more points on the queue. I think you can use a stack also if it's simpler. But when computers where slow and you saw it working the queue looked cooler.

The advantage of this method is the queue is usually very small because you are only queuing a small number of points. In fact for convex objects it maxes out at two. You are also working directly on your picture matrix so it should be faster. This is kind of the classic flood fill.  You defiantly won't even come close to overflowing your stack . I had to do this in 8086 ASM way back when and even there it wasn't too hard.

If you want to see the code I can write it up.

 

Edited by Gnollrunner

Share this post


Link to post
Share on other sites
On 12/29/2018 at 8:14 AM, _WeirdCat_ said:

when creating floodfill algorithm which is done by calling recursive function

Aside: flood fill was probably the single most common whiteboard coding interview question at the time when I joined Amazon.

Learning both how to implement all the recursive search algorithms, and how to convert them to the iterative version using a stack, will serve you well in the future.

Share this post


Link to post
Share on other sites

It's sound stupid, but programm can crash, when you call too many functions and overflow stack by stack allocs. It could be ~260 000 recursion without return-state. Main goal of Amazon and other huge companies is - you will work all your life and remember all and help everyone if needed. It's very long term contract.

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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!