Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #120329 > unrolled thread

thread about the pros and cons of lambdas, but more about cons

Back to article view | Back to comp.lang.c++

Contents

  thread about the pros and cons of lambdas, but more about cons Michael S <already5chosen@yahoo.com> - 2024-09-25 19:54 +0300
    Re: thread about the pros and cons of lambdas, but more about cons Bonita Montero <Bonita.Montero@gmail.com> - 2024-09-25 19:17 +0200
    Re: thread about the pros and cons of lambdas, but more about cons Bonita Montero <Bonita.Montero@gmail.com> - 2024-09-25 19:55 +0200
    Re: thread about the pros and cons of lambdas, but more about cons Paavo Helde <eesnimi@osa.pri.ee> - 2024-09-25 22:53 +0300
      Re: thread about the pros and cons of lambdas, but more about cons Michael S <already5chosen@yahoo.com> - 2024-09-25 23:30 +0300
        Re: thread about the pros and cons of lambdas, but more about cons Paavo Helde <eesnimi@osa.pri.ee> - 2024-09-26 00:04 +0300
          Re: thread about the pros and cons of lambdas, but more about cons Michael S <already5chosen@yahoo.com> - 2024-09-26 11:17 +0300
          Re: thread about the pros and cons of lambdas, but more about cons Paavo Helde <eesnimi@osa.pri.ee> - 2024-09-26 11:25 +0300
            Re: thread about the pros and cons of lambdas, but more about cons Bonita Montero <Bonita.Montero@gmail.com> - 2024-09-26 10:28 +0200
              Re: thread about the pros and cons of lambdas, but more about cons Paavo Helde <eesnimi@osa.pri.ee> - 2024-09-26 11:49 +0300
            Re: thread about the pros and cons of lambdas, but more about cons Michael S <already5chosen@yahoo.com> - 2024-09-26 11:38 +0300
    Re: thread about the pros and cons of lambdas, but more about cons Ben Bacarisse <ben@bsb.me.uk> - 2024-09-25 23:13 +0100
      Re: thread about the pros and cons of lambdas, but more about cons Ben Bacarisse <ben@bsb.me.uk> - 2024-09-25 23:28 +0100
        Re: thread about the pros and cons of lambdas, but more about cons Michael S <already5chosen@yahoo.com> - 2024-09-26 10:41 +0300
          Re: thread about the pros and cons of lambdas, but more about cons David Brown <david.brown@hesbynett.no> - 2024-09-26 10:29 +0200
            Re: thread about the pros and cons of lambdas, but more about cons Bonita Montero <Bonita.Montero@gmail.com> - 2024-09-26 11:35 +0200
              Re: thread about the pros and cons of lambdas, but more about cons David Brown <david.brown@hesbynett.no> - 2024-09-26 13:27 +0200
                Re: thread about the pros and cons of lambdas, but more about cons Bonita Montero <Bonita.Montero@gmail.com> - 2024-09-26 13:31 +0200
                  Re: thread about the pros and cons of lambdas, but more about cons Michael S <already5chosen@yahoo.com> - 2024-09-26 15:25 +0300
                    Re: thread about the pros and cons of lambdas, but more about cons Bonita Montero <Bonita.Montero@gmail.com> - 2024-09-26 14:58 +0200
                      Re: thread about the pros and cons of lambdas, but more about cons Michael S <already5chosen@yahoo.com> - 2024-09-26 16:53 +0300
                        Re: thread about the pros and cons of lambdas, but more about cons Bonita Montero <Bonita.Montero@gmail.com> - 2024-09-26 15:54 +0200
          Re: thread about the pros and cons of lambdas, but more about cons Michael S <already5chosen@yahoo.com> - 2024-09-27 16:55 +0300
        Re: thread about the pros and cons of lambdas, but more about cons Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-09-26 10:01 -0700
          Re: thread about the pros and cons of lambdas, but more about cons Bonita Montero <Bonita.Montero@gmail.com> - 2024-09-26 19:04 +0200
          Re: thread about the pros and cons of lambdas, but more about cons Michael S <already5chosen@yahoo.com> - 2024-09-26 20:20 +0300
            Re: thread about the pros and cons of lambdas, but more about cons Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-09-26 10:38 -0700
              Re: thread about the pros and cons of lambdas, but more about cons Michael S <already5chosen@yahoo.com> - 2024-09-27 16:27 +0300
                Re: thread about the pros and cons of lambdas, but more about cons Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-09-28 04:06 -0700
      Re: thread about the pros and cons of lambdas, but more about cons Michael S <already5chosen@yahoo.com> - 2024-09-26 10:58 +0300
      Re: thread about the pros and cons of lambdas, but more about cons Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-09-26 10:27 -0700
        Re: thread about the pros and cons of lambdas, but more about cons Bonita Montero <Bonita.Montero@gmail.com> - 2024-09-26 19:32 +0200
    Re: thread about the pros and cons of lambdas, but more about cons Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-09-26 14:09 -0700
      Re: thread about the pros and cons of lambdas, but more about cons Michael S <already5chosen@yahoo.com> - 2024-09-27 16:15 +0300
        Re: thread about the pros and cons of lambdas, but more about cons Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-09-28 04:25 -0700

Page 1 of 2  [1] 2  Next page →

#120329 — thread about the pros and cons of lambdas, but more about cons

On Wed, 25 Sep 2024 17:14:09 +0200
David Brown <david.brown@hesbynett.no> wrote:

> On 25/09/2024 16:14, Michael S wrote:
> > On Wed, 25 Sep 2024 15:04:27 +0200
> > David Brown <david.brown@hesbynett.no> wrote:
> >   
> >> On 25/09/2024 14:39, Bonita Montero wrote:  
> >>> Am 25.09.2024 um 14:36 schrieb David Brown:
> >>>      
> >>>> That's reasonable if you have something useful to say.  Telling
> >>>> people that they can use lambdas here is /not/ useful.  We all
> >>>> know we could use lambdas, but that is totally missing the point
> >>>> of the discussion.  
> >>>
> >>> I guess Michael S doesn't know this, otherwrite he would have used
> >>> a lambda himself. That's pre-C++11-style and maybe his knowledge
> >>> is from then.
> >>>      
> >>
> >> Seriously?  Sometimes I wonder if you ever bother reading other
> >> people's posts.
> >>
> >> Of /course/ Michael knows he could use a lambda there.  
> > 
> > [O.T.]
> > I know that they can be used, but I never use lambdas myself.
> > Because of that my knowledge is theoretical and I am not fluent with
> > syntax.
> > 
> > Why I am not using lambdas myself? Because I think that lambda with
> > captures makes code harder to follow and to understand (that's my
> > 1st hand experience from reading big corpus of Ada83 code. Ada83
> > does not have lambdas, but it has nested procedures that can access
> > parent's variable, similarly to lambda with [&] default capture).
> > And lambda without captures does not provide enough of advantage
> > over named functions to bother with mastering new concept.
> >   
> 
> It's maybe worth having another thread about the pros and cons of 
> lambdas, but that really should be a new thread.
> 


Some time ago on comp.lang.c we had very long thread about floodfill4
algorithm (that both myself and TimR took more seriously than an
issue deserves, but that's off topic).

Today I coded two implementations of original brute-force recursive
algorithm.

// floodfill_recursive_nested.
// Implementation is in none-tricky C++
// Very similar to what can be done in C

#include <cstddef>

int floodfill4(
  unsigned char *grey,
  int width, int height,
  int x, int y,
  unsigned char target, unsigned char dest)
{
  if (width < 1 || height < 1)
    return 0;
  if (x < 0 || x >= width || y < 0 || y >= height)
    return 0;

  size_t w = width, h = height;
  if (grey[y*w+x] != target)
    return 0;

  struct {
    unsigned char *grey;
    size_t width, height;
    unsigned char target, dest;
    void core(size_t x, size_t y) const
    {
      if (x < width && y < height) {
        auto idx = y*width+x;
        if (grey[idx] == target) {
          grey[idx] = dest;
          core(x - 1, y);
          core(x + 1, y);
          core(x, y - 1);
          core(x, y + 1);
        }
      }
    }
  } context = {
    .grey = grey,
    .width = w, .height = h,
    .target = target, .dest = dest,
  };
  context.core(x, y);
  return 1;
}

// end of floodfill_recursive_nested.



// floodfill_recursive_lambda.
// Implementation in tricky C++
// C can not do it

#include <cstddef>

int floodfill4(
  unsigned char *grey,
  int width, int height,
  int x, int y,
  unsigned char target, unsigned char dest)
{
  if (width < 1 || height < 1)
    return 0;
  if (x < 0 || x >= width || y < 0 || y >= height)
    return 0;

  size_t w = width, h = height;
  if (grey[y*w+x] != target)
    return 0;

  auto core = [=] (auto& a_ref, size_t x, size_t y) {
    if (x >= w || y >= h)
      return;
    auto idx = y*w+x;
    if (grey[idx] == target) {
      grey[idx] = dest;
      a_ref(a_ref, x - 1, y);
      a_ref(a_ref, x + 1, y);
      a_ref(a_ref, x, y - 1);
      a_ref(a_ref, x, y + 1);
    }
  };
  core(core, x, y);
  return 1;
}

// end of floodfill_recursive_lambda.


In the second variant in order to make it compile at all I had to uses
very dirty trick with lambda passed as parameter to itself. I copied it
from Stack Overflow, but don't pretend to understand why it works and
why it needed in the first place.

But that's only part of the story.
The other part is that the first variant is 1.2x faster.

[toc] | [next] | [standalone]

#120330

I've only pros about the functional programming which is possible since
C++11. I've already shown a function in another thread from which you
can see how I use functional programming in C++:

void fileList( wchar_t const *path, std::function<bool ( 
WIN32_FIND_DATAW const & )> const &fn, DWORD *pdwErr )
{
	using namespace std;
	if( pdwErr )
		*pdwErr = NO_ERROR;
	WIN32_FIND_DATAW fd;
	HANDLE hFind = FindFirstFileW( path, &fd );
	auto err = [&]<bool Initiate>( bool_constant<Initiate> )
	{
		DWORD dwErr = GetLastError();
		if( dwErr == (Initiate ? ERROR_FILE_NOT_FOUND : ERROR_NO_MORE_FILES) )
			return;
		if( !pdwErr )
		{
			constexpr char const *ERR = Initiate ? "FindFirstFile() failed: \"" : 
"FindNextFile() failed: \"";
			throw system_error( dwErr, system_category(), (ostringstream() << ERR 
<< wideCharToMultiByte( path ) << "\"").str().c_str() );
		}
		*pdwErr = dwErr;
	};
	if( hFind == INVALID_HANDLE_VALUE )
		return (void)err( true_type() );
	invoke_on_destruct closeFind( [&]() { FindClose( hFind ); } );
	do
		if( wcscmp( fd.cFileName, L"." ) == 0 || wcscmp( fd.cFileName, L".." ) 
== 0 )
			continue;
		else if( !fn( fd ) )
			return;
	while( FindNextFileW( hFind, &fd ) );
	err( false_type() );
}

The function lists files in a directory with the Win32-API. It has
a runtime polymophic callback thar gets the WIN32_FIND_DATAW-ojects.
It has two places where it deals with the error-handling, either
by trowing a system_error exception or if *pdwErr is non-null, by
setting an error-code. This error handling is encapsulated in a
lambda to prevent mostly redundant code. This lambda is generic
because there are two different error codes which aren't actually
errors, but valid states.
And I'm using sth. like experimental::scope_exit to close the find
handle. But this scope_exit-like class is more flexible since you
can chain multiple of them and if an exception is throws multiple
changes to a data structure are "rolled back" and if you call dis-
able() on the last in the chain everything is "committed".

[toc] | [prev] | [next] | [standalone]

#120332

I just noticed who started this thread. Maybe you don't trust lambdas
because lambdas implement a lot of functionality with very little
syntax. This may seem much more understandable in a hand-written class
with a call operator, but once you get into the topic and really work
with it a lot, you really learn to appreciate this minimalist syntax.
At this point I can recommend the book "C++ Lambda Story" by Bartłomiej
Filipek.

[toc] | [prev] | [next] | [standalone]

#120337

On 25.09.2024 19:54, Michael S wrote:
> On Wed, 25 Sep 2024 17:14:09 +0200
> David Brown <david.brown@hesbynett.no> wrote:
> 
>> On 25/09/2024 16:14, Michael S wrote:
>>> On Wed, 25 Sep 2024 15:04:27 +0200
>>> David Brown <david.brown@hesbynett.no> wrote:
>>>    
>>>> On 25/09/2024 14:39, Bonita Montero wrote:
>>>>> Am 25.09.2024 um 14:36 schrieb David Brown:
>>>>>       
>>>>>> That's reasonable if you have something useful to say.  Telling
>>>>>> people that they can use lambdas here is /not/ useful.  We all
>>>>>> know we could use lambdas, but that is totally missing the point
>>>>>> of the discussion.
>>>>>
>>>>> I guess Michael S doesn't know this, otherwrite he would have used
>>>>> a lambda himself. That's pre-C++11-style and maybe his knowledge
>>>>> is from then.
>>>>>       
>>>>
>>>> Seriously?  Sometimes I wonder if you ever bother reading other
>>>> people's posts.
>>>>
>>>> Of /course/ Michael knows he could use a lambda there.
>>>
>>> [O.T.]
>>> I know that they can be used, but I never use lambdas myself.
>>> Because of that my knowledge is theoretical and I am not fluent with
>>> syntax.
>>>
>>> Why I am not using lambdas myself? Because I think that lambda with
>>> captures makes code harder to follow and to understand (that's my
>>> 1st hand experience from reading big corpus of Ada83 code. Ada83
>>> does not have lambdas, but it has nested procedures that can access
>>> parent's variable, similarly to lambda with [&] default capture).
>>> And lambda without captures does not provide enough of advantage
>>> over named functions to bother with mastering new concept.
>>>    
>>
>> It's maybe worth having another thread about the pros and cons of
>> lambdas, but that really should be a new thread.
>>
> 
> 
> Some time ago on comp.lang.c we had very long thread about floodfill4
> algorithm (that both myself and TimR took more seriously than an
> issue deserves, but that's off topic).
> 
> Today I coded two implementations of original brute-force recursive
> algorithm.
> 
> // floodfill_recursive_nested.
> // Implementation is in none-tricky C++
> // Very similar to what can be done in C
> 
> #include <cstddef>
> 
> int floodfill4(
>    unsigned char *grey,
>    int width, int height,
>    int x, int y,
>    unsigned char target, unsigned char dest)
> {
>    if (width < 1 || height < 1)
>      return 0;
>    if (x < 0 || x >= width || y < 0 || y >= height)
>      return 0;
> 
>    size_t w = width, h = height;
>    if (grey[y*w+x] != target)
>      return 0;
> 
>    struct {
>      unsigned char *grey;
>      size_t width, height;
>      unsigned char target, dest;
>      void core(size_t x, size_t y) const
>      {
>        if (x < width && y < height) {
>          auto idx = y*width+x;
>          if (grey[idx] == target) {
>            grey[idx] = dest;
>            core(x - 1, y);
>            core(x + 1, y);
>            core(x, y - 1);
>            core(x, y + 1);
>          }
>        }
>      }
>    } context = {
>      .grey = grey,
>      .width = w, .height = h,
>      .target = target, .dest = dest,
>    };
>    context.core(x, y);
>    return 1;
> }
> 
> // end of floodfill_recursive_nested.
> 
> 
> 
> // floodfill_recursive_lambda.
> // Implementation in tricky C++
> // C can not do it
> 
> #include <cstddef>
> 
> int floodfill4(
>    unsigned char *grey,
>    int width, int height,
>    int x, int y,
>    unsigned char target, unsigned char dest)
> {
>    if (width < 1 || height < 1)
>      return 0;
>    if (x < 0 || x >= width || y < 0 || y >= height)
>      return 0;
> 
>    size_t w = width, h = height;
>    if (grey[y*w+x] != target)
>      return 0;
> 
>    auto core = [=] (auto& a_ref, size_t x, size_t y) {
>      if (x >= w || y >= h)
>        return;
>      auto idx = y*w+x;
>      if (grey[idx] == target) {
>        grey[idx] = dest;
>        a_ref(a_ref, x - 1, y);
>        a_ref(a_ref, x + 1, y);
>        a_ref(a_ref, x, y - 1);
>        a_ref(a_ref, x, y + 1);
>      }
>    };
>    core(core, x, y);
>    return 1;
> }
> 
> // end of floodfill_recursive_lambda.
> 
> 
> In the second variant in order to make it compile at all I had to uses
> very dirty trick with lambda passed as parameter to itself. I copied it
> from Stack Overflow, but don't pretend to understand why it works and
> why it needed in the first place.
> 
> But that's only part of the story.
> The other part is that the first variant is 1.2x faster.

This is called a strawman argument. You invent an example where the 
lambda does not really suit and is slower than an alternative, then 
attack it.

Solution is simple: use lambdas where they fit.

[toc] | [prev] | [next] | [standalone]

#120338

On Wed, 25 Sep 2024 22:53:47 +0300
Paavo Helde <eesnimi@osa.pri.ee> wrote:

> 
> This is called a strawman argument. You invent an example where the 
> lambda does not really suit and is slower than an alternative, then 
> attack it.
> 
> Solution is simple: use lambdas where they fit.
> 

Can you give me one reason why writing recursive lambdas in C++ can not
be streight-forward?
That's how lambda-base recursive code that is 100% equivalent of above
C++ looks in Go. Simpler, isn't it?

  var ff4 func(x, y uintptr)
  ff4 = func(x, y uintptr) {
    if x >= w || y >= h {
      return
    }
    if img[w*y+x] != target {
      return
    }
    img[w*y+x] = dest
    ff4(x-1, y)
    ff4(x+1, y)
    ff4(x, y-1)
    ff4(x, y+1)
  }

[toc] | [prev] | [next] | [standalone]

#120339

On 25.09.2024 23:30, Michael S wrote:
> On Wed, 25 Sep 2024 22:53:47 +0300
> Paavo Helde <eesnimi@osa.pri.ee> wrote:
> 
>>
>> This is called a strawman argument. You invent an example where the
>> lambda does not really suit and is slower than an alternative, then
>> attack it.
>>
>> Solution is simple: use lambdas where they fit.
>>
> 
> Can you give me one reason why writing recursive lambdas in C++ can not
> be streight-forward?
> That's how lambda-base recursive code that is 100% equivalent of above
> C++ looks in Go. Simpler, isn't it?
> 
>    var ff4 func(x, y uintptr)
>    ff4 = func(x, y uintptr) {
>      if x >= w || y >= h {
>        return
>      }
>      if img[w*y+x] != target {
>        return
>      }
>      img[w*y+x] = dest
>      ff4(x-1, y)
>      ff4(x+1, y)
>      ff4(x, y-1)
>      ff4(x, y+1)
>    }

Looks simpler, but not sure it actually is, given that access to the 
"outer" variables seems to be not encapsulated or controlled in any way. 
Probably this is an equivalent to a C++ free function with global or 
thread-local variables, not to a C++ lambda.


There are many things in C++ which I do not like and many things which 
I'm sure could work better. However, my task as a software engineer is 
to make the best use of the tools which I have got. With C++ this means 
avoiding use or misuse of very many of its features.

[toc] | [prev] | [next] | [standalone]

#120349

On Thu, 26 Sep 2024 00:04:03 +0300
Paavo Helde <eesnimi@osa.pri.ee> wrote:

> On 25.09.2024 23:30, Michael S wrote:
> > On Wed, 25 Sep 2024 22:53:47 +0300
> > Paavo Helde <eesnimi@osa.pri.ee> wrote:
> >   
> >>
> >> This is called a strawman argument. You invent an example where the
> >> lambda does not really suit and is slower than an alternative, then
> >> attack it.
> >>
> >> Solution is simple: use lambdas where they fit.
> >>  
> > 
> > Can you give me one reason why writing recursive lambdas in C++ can
> > not be streight-forward?
> > That's how lambda-base recursive code that is 100% equivalent of
> > above C++ looks in Go. Simpler, isn't it?
> > 
> >    var ff4 func(x, y uintptr)
> >    ff4 = func(x, y uintptr) {
> >      if x >= w || y >= h {
> >        return
> >      }
> >      if img[w*y+x] != target {
> >        return
> >      }
> >      img[w*y+x] = dest
> >      ff4(x-1, y)
> >      ff4(x+1, y)
> >      ff4(x, y-1)
> >      ff4(x, y+1)
> >    }  
> 
> Looks simpler, but not sure it actually is, given that access to the 
> "outer" variables seems to be not encapsulated or controlled in any
> way.

Correct. Go does has no fine access control that is available in C++.
Any lambda in Go has access to all variables at scope of its
declaration/definition.

> Probably this is an equivalent to a C++ free function with
> global or thread-local variables, not to a C++ lambda.
> 

That's incorrect.
Lambda in Go is less controlled than in C++, but it is not less
powerful. More like more powerful. 
According to my understanding, in Go one can pass lambda to goroutine
(which is more similar to C++ thread than to C++ coroutine) then exit
the calling function and things will still work as naively expected.
I don't believe that you can do it in C++, or, at least you can't do it
if your lambda has captures accessed by reference.
Pay attention, I didn't try it, just skimmed docs, so I could be wrong.

> 
> There are many things in C++ which I do not like and many things
> which I'm sure could work better. However, my task as a software
> engineer is to make the best use of the tools which I have got. With
> C++ this means avoiding use or misuse of very many of its features.
> 

Of course, I agree with that. Where I disagree is that IMO in case of
lambdas almost every use carries at least a seed of misuse So, on
balance, C++ language would have been better without them.

[toc] | [prev] | [next] | [standalone]

#120352

On 26.09.2024 00:04, Paavo Helde wrote:
> On 25.09.2024 23:30, Michael S wrote:
>> On Wed, 25 Sep 2024 22:53:47 +0300
>> Paavo Helde <eesnimi@osa.pri.ee> wrote:
>>
>>>
>>> This is called a strawman argument. You invent an example where the
>>> lambda does not really suit and is slower than an alternative, then
>>> attack it.
>>>
>>> Solution is simple: use lambdas where they fit.
>>>
>>
>> Can you give me one reason why writing recursive lambdas in C++ can not
>> be streight-forward?
>> That's how lambda-base recursive code that is 100% equivalent of above
>> C++ looks in Go. Simpler, isn't it?
>>
>>    var ff4 func(x, y uintptr)
>>    ff4 = func(x, y uintptr) {
>>      if x >= w || y >= h {
>>        return
>>      }
>>      if img[w*y+x] != target {
>>        return
>>      }
>>      img[w*y+x] = dest
>>      ff4(x-1, y)
>>      ff4(x+1, y)
>>      ff4(x, y-1)
>>      ff4(x, y+1)
>>    }
> 
> Looks simpler, but not sure it actually is, given that access to the 
> "outer" variables seems to be not encapsulated or controlled in any way. 
> Probably this is an equivalent to a C++ free function with global or 
> thread-local variables, not to a C++ lambda.
> 
> 
> There are many things in C++ which I do not like and many things which 
> I'm sure could work better. However, my task as a software engineer is 
> to make the best use of the tools which I have got. With C++ this means 
> avoiding use or misuse of very many of its features.
> 

PS. One of things I have learned to avoid in C++ is heavy recursion, 
which is known to be slow (on x86 at least) and can easily cause stack 
overflows. I just tested this simplistic fully recursive floodfill4 and 
both versions run out of stack already with so small as 200x200 
uniformly filled images, in a VS2022 x86_64 program with default settings.

So this solution is totally unacceptable for production code, and all 
talk about its simplicity (or not) is purely academic.

[toc] | [prev] | [next] | [standalone]

#120353

Am 26.09.2024 um 10:25 schrieb Paavo Helde:

> PS. One of things I have learned to avoid in C++ is heavy recursion, 
> which is known to be slow (on x86 at least) and can easily cause stack 
> overflows. ...

Recursion ain't slow and stack you never have so much recursion levels
that a stack overlow ist realistic. Stack overflows are usually program-
ming errors like a missing termination condition with a recursion or
you do too much alloca().

[toc] | [prev] | [next] | [standalone]

#120357

On 26.09.2024 11:28, Bonita Montero wrote:
> Am 26.09.2024 um 10:25 schrieb Paavo Helde:
> 
>> PS. One of things I have learned to avoid in C++ is heavy recursion, 
>> which is known to be slow (on x86 at least) and can easily cause stack 
>> overflows. ...
> 
> Recursion ain't slow and stack you never have so much recursion levels
> that a stack overlow ist realistic. Stack overflows are usually program-
> ming errors like a missing termination condition with a recursion or
> you do too much alloca().
> 

You are funny, thanks for the laughs!

But seriously, the recursion stack frame size in the original floodfill4 
examples in top of this thread is 64 and 80 bytes, respectively (MSVC 
adds its own security checks in each frame by default. that's why these 
are larger than expected). The default stack size in MSVC++ is 1MB. This 
means ca 17,000 or 13,000 recursions, which means these algorithms only 
cope with contiguous objects of so many pixels. Do you really think this 
is an unrealistically large number? It would be about 0.1 % of your 
average phone click.

[toc] | [prev] | [next] | [standalone]

#120355

On Thu, 26 Sep 2024 11:25:05 +0300
Paavo Helde <eesnimi@osa.pri.ee> wrote:

> On 26.09.2024 00:04, Paavo Helde wrote:
> > On 25.09.2024 23:30, Michael S wrote:  
> >> On Wed, 25 Sep 2024 22:53:47 +0300
> >> Paavo Helde <eesnimi@osa.pri.ee> wrote:
> >>  
> >>>
> >>> This is called a strawman argument. You invent an example where
> >>> the lambda does not really suit and is slower than an
> >>> alternative, then attack it.
> >>>
> >>> Solution is simple: use lambdas where they fit.
> >>>  
> >>
> >> Can you give me one reason why writing recursive lambdas in C++
> >> can not be streight-forward?
> >> That's how lambda-base recursive code that is 100% equivalent of
> >> above C++ looks in Go. Simpler, isn't it?
> >>
> >>    var ff4 func(x, y uintptr)
> >>    ff4 = func(x, y uintptr) {
> >>      if x >= w || y >= h {
> >>        return
> >>      }
> >>      if img[w*y+x] != target {
> >>        return
> >>      }
> >>      img[w*y+x] = dest
> >>      ff4(x-1, y)
> >>      ff4(x+1, y)
> >>      ff4(x, y-1)
> >>      ff4(x, y+1)
> >>    }  
> > 
> > Looks simpler, but not sure it actually is, given that access to
> > the "outer" variables seems to be not encapsulated or controlled in
> > any way. Probably this is an equivalent to a C++ free function with
> > global or thread-local variables, not to a C++ lambda.
> > 
> > 
> > There are many things in C++ which I do not like and many things
> > which I'm sure could work better. However, my task as a software
> > engineer is to make the best use of the tools which I have got.
> > With C++ this means avoiding use or misuse of very many of its
> > features. 
> 
> PS. One of things I have learned to avoid in C++ is heavy recursion, 
> which is known to be slow (on x86 at least) and can easily cause
> stack overflows. I just tested this simplistic fully recursive
> floodfill4 and both versions run out of stack already with so small
> as 200x200 uniformly filled images, in a VS2022 x86_64 program with
> default settings.
> 

When I test it on Windows the stack size is set to 8MB.
That's enough for 200x200.
It seems, on many x86-64 Linuxes 8MB is a default.

> So this solution is totally unacceptable for production code, and all 
> talk about its simplicity (or not) is purely academic.
> 

It depends.
Sometimes one knows up front that the images are small.
Yet sometimes one knows that in his environment stack is allowed to be
huge.
For example, Go on x86-64 sets default stack limit to 1 GB.
But more often what you said is correct.

[toc] | [prev] | [next] | [standalone]

#120340

Michael S <already5chosen@yahoo.com> writes:

> On Wed, 25 Sep 2024 17:14:09 +0200
> David Brown <david.brown@hesbynett.no> wrote:
>
>> On 25/09/2024 16:14, Michael S wrote:
>> > On Wed, 25 Sep 2024 15:04:27 +0200
>> > David Brown <david.brown@hesbynett.no> wrote:
>> >   
>> >> On 25/09/2024 14:39, Bonita Montero wrote:  
>> >>> Am 25.09.2024 um 14:36 schrieb David Brown:
>> >>>      
>> >>>> That's reasonable if you have something useful to say.  Telling
>> >>>> people that they can use lambdas here is /not/ useful.  We all
>> >>>> know we could use lambdas, but that is totally missing the point
>> >>>> of the discussion.  
>> >>>
>> >>> I guess Michael S doesn't know this, otherwrite he would have used
>> >>> a lambda himself. That's pre-C++11-style and maybe his knowledge
>> >>> is from then.
>> >>>      
>> >>
>> >> Seriously?  Sometimes I wonder if you ever bother reading other
>> >> people's posts.
>> >>
>> >> Of /course/ Michael knows he could use a lambda there.  
>> > 
>> > [O.T.]
>> > I know that they can be used, but I never use lambdas myself.
>> > Because of that my knowledge is theoretical and I am not fluent with
>> > syntax.
>> > 
>> > Why I am not using lambdas myself? Because I think that lambda with
>> > captures makes code harder to follow and to understand (that's my
>> > 1st hand experience from reading big corpus of Ada83 code. Ada83
>> > does not have lambdas, but it has nested procedures that can access
>> > parent's variable, similarly to lambda with [&] default capture).
>> > And lambda without captures does not provide enough of advantage
>> > over named functions to bother with mastering new concept.
>> >   
>> 
>> It's maybe worth having another thread about the pros and cons of 
>> lambdas, but that really should be a new thread.
>> 
>
>
> Some time ago on comp.lang.c we had very long thread about floodfill4
> algorithm (that both myself and TimR took more seriously than an
> issue deserves, but that's off topic).
>
> Today I coded two implementations of original brute-force recursive
> algorithm.
>
> // floodfill_recursive_nested.
> // Implementation is in none-tricky C++
> // Very similar to what can be done in C
>
> #include <cstddef>
>
> int floodfill4(
>   unsigned char *grey,
>   int width, int height,
>   int x, int y,
>   unsigned char target, unsigned char dest)
> {
>   if (width < 1 || height < 1)
>     return 0;
>   if (x < 0 || x >= width || y < 0 || y >= height)
>     return 0;
>
>   size_t w = width, h = height;
>   if (grey[y*w+x] != target)
>     return 0;
>
>   struct {
>     unsigned char *grey;
>     size_t width, height;
>     unsigned char target, dest;
>     void core(size_t x, size_t y) const
>     {
>       if (x < width && y < height) {
>         auto idx = y*width+x;
>         if (grey[idx] == target) {
>           grey[idx] = dest;
>           core(x - 1, y);
>           core(x + 1, y);
>           core(x, y - 1);
>           core(x, y + 1);
>         }
>       }
>     }
>   } context = {
>     .grey = grey,
>     .width = w, .height = h,
>     .target = target, .dest = dest,
>   };
>   context.core(x, y);
>   return 1;
> }
>
> // end of floodfill_recursive_nested.
>
>
>
> // floodfill_recursive_lambda.
> // Implementation in tricky C++
> // C can not do it
>
> #include <cstddef>
>
> int floodfill4(
>   unsigned char *grey,
>   int width, int height,
>   int x, int y,
>   unsigned char target, unsigned char dest)
> {
>   if (width < 1 || height < 1)
>     return 0;
>   if (x < 0 || x >= width || y < 0 || y >= height)
>     return 0;
>
>   size_t w = width, h = height;
>   if (grey[y*w+x] != target)
>     return 0;
>
>   auto core = [=] (auto& a_ref, size_t x, size_t y) {
>     if (x >= w || y >= h)
>       return;
>     auto idx = y*w+x;
>     if (grey[idx] == target) {
>       grey[idx] = dest;
>       a_ref(a_ref, x - 1, y);
>       a_ref(a_ref, x + 1, y);
>       a_ref(a_ref, x, y - 1);
>       a_ref(a_ref, x, y + 1);
>     }
>   };
>   core(core, x, y);
>   return 1;
> }
>
> // end of floodfill_recursive_lambda.
>
>
> In the second variant in order to make it compile at all I had to uses
> very dirty trick with lambda passed as parameter to itself. I copied it
> from Stack Overflow, but don't pretend to understand why it works and
> why it needed in the first place.

For this part the answer is simple.  The lambda only captures names that
are defined at its point of definition, and core is not defined until
the end of the declarator which include the initialisation -- the lambda
you are defining.  The lambda stored in 'core', can't therefore refer to
the name core because core was not defined before the lambda.  You can,
instead, do this (untested):

  #include <functional>
   
  int floodfill4(
    unsigned char *grey,
    int width, int height,
    int x, int y,
    unsigned char target, unsigned char dest)
  {
    if (width < 1 || height < 1)
      return 0;
    if (x < 0 || x >= width || y < 0 || y >= height)
      return 0;
   
    size_t w = width, h = height;
    if (grey[y*w+x] != target)
      return 0;
   
    std::function<void(size_t, size_t)> core;
    core = [=] (size_t x, size_t y) {
      if (x >= w || y >= h)
        return;
      auto idx = y*w+x;
      if (grey[idx] == target) {
        grey[idx] = dest;
        core(x - 1, y);
        core(x + 1, y);
        core(x, y - 1);
        core(x, y + 1);
      }
    };
    core(x, y);
    return 1;
  }

> But that's only part of the story.
> The other part is that the first variant is 1.2x faster.

Interesting, though this is not really what a lambda is for.  What you
want here is a plain lexical nested function -- it's purpose being just
an auxiliary function that can refer to the outer scope so as to require
fewer parameters.

It would be interesting to see is gcc's nested function extension
produced something that was faster than a lambda.

Note: this is a very old problem and actually pre-dates the computing
era.  Combinatory logic had to come up with the Y combinator to make
recursive "functions", and (slightly more recently) some Lisps have two
forms of 'let' to deal with this issue.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#120341

Ben Bacarisse <ben@bsb.me.uk> writes:

> ... You can,
> instead, do this (untested):

I should have tested!  Of course you have to change the capture (at
least for core) from '=' to '&':

>   #include <functional>
>    
>   int floodfill4(
>     unsigned char *grey,
>     int width, int height,
>     int x, int y,
>     unsigned char target, unsigned char dest)
>   {
>     if (width < 1 || height < 1)
>       return 0;
>     if (x < 0 || x >= width || y < 0 || y >= height)
>       return 0;
>    
>     size_t w = width, h = height;
>     if (grey[y*w+x] != target)
>       return 0;
>    
>     std::function<void(size_t, size_t)> core;
>     core = [&] (size_t x, size_t y) {
Corrected-----^
>       if (x >= w || y >= h)
>         return;
>       auto idx = y*w+x;
>       if (grey[idx] == target) {
>         grey[idx] = dest;
>         core(x - 1, y);
>         core(x + 1, y);
>         core(x, y - 1);
>         core(x, y + 1);
>       }
>     };
>     core(x, y);
>     return 1;
>   }

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#120347

On Wed, 25 Sep 2024 23:28:57 +0100
Ben Bacarisse <ben@bsb.me.uk> wrote:

> Ben Bacarisse <ben@bsb.me.uk> writes:
> 
> > ... You can,
> > instead, do this (untested):  
> 
> I should have tested!  Of course you have to change the capture (at
> least for core) from '=' to '&':
> 
> >   #include <functional>
> >    
> >   int floodfill4(
> >     unsigned char *grey,
> >     int width, int height,
> >     int x, int y,
> >     unsigned char target, unsigned char dest)
> >   {
> >     if (width < 1 || height < 1)
> >       return 0;
> >     if (x < 0 || x >= width || y < 0 || y >= height)
> >       return 0;
> >    
> >     size_t w = width, h = height;
> >     if (grey[y*w+x] != target)
> >       return 0;
> >    
> >     std::function<void(size_t, size_t)> core;
> >     core = [&] (size_t x, size_t y) {  
> Corrected-----^
> >       if (x >= w || y >= h)
> >         return;
> >       auto idx = y*w+x;
> >       if (grey[idx] == target) {
> >         grey[idx] = dest;
> >         core(x - 1, y);
> >         core(x + 1, y);
> >         core(x, y - 1);
> >         core(x, y + 1);
> >       }
> >     };
> >     core(x, y);
> >     return 1;
> >   }  
> 

That's where I started.
It is approximately twice slower than tricky version with [&].
And tricky [&] almost 20% slower than tricky [=].
I didn't try to understand what std::function thing is, but fast it
isn't.

[toc] | [prev] | [next] | [standalone]

#120354

On 26/09/2024 09:41, Michael S wrote:
> On Wed, 25 Sep 2024 23:28:57 +0100
> Ben Bacarisse <ben@bsb.me.uk> wrote:
> 
>> Ben Bacarisse <ben@bsb.me.uk> writes:
>>
>>> ... You can,
>>> instead, do this (untested):
>>
>> I should have tested!  Of course you have to change the capture (at
>> least for core) from '=' to '&':
>>
>>>    #include <functional>
>>>     
>>>    int floodfill4(
>>>      unsigned char *grey,
>>>      int width, int height,
>>>      int x, int y,
>>>      unsigned char target, unsigned char dest)
>>>    {
>>>      if (width < 1 || height < 1)
>>>        return 0;
>>>      if (x < 0 || x >= width || y < 0 || y >= height)
>>>        return 0;
>>>     
>>>      size_t w = width, h = height;
>>>      if (grey[y*w+x] != target)
>>>        return 0;
>>>     
>>>      std::function<void(size_t, size_t)> core;
>>>      core = [&] (size_t x, size_t y) {
>> Corrected-----^
>>>        if (x >= w || y >= h)
>>>          return;
>>>        auto idx = y*w+x;
>>>        if (grey[idx] == target) {
>>>          grey[idx] = dest;
>>>          core(x - 1, y);
>>>          core(x + 1, y);
>>>          core(x, y - 1);
>>>          core(x, y + 1);
>>>        }
>>>      };
>>>      core(x, y);
>>>      return 1;
>>>    }
>>
> 
> That's where I started.
> It is approximately twice slower than tricky version with [&].
> And tricky [&] almost 20% slower than tricky [=].
> I didn't try to understand what std::function thing is, but fast it
> isn't.
> 

std::function<> can be very flexible, but it is often costly at 
run-time.  There are situations where the compiler can optimise away the 
overheads, but often at least some remains.

[toc] | [prev] | [next] | [standalone]

#120362

Am 26.09.2024 um 10:29 schrieb David Brown:

> std::function<> can be very flexible, but it is often costly at run- 
> time.  There are situations where the compiler can optimise away the 
> overheads, but often at least some remains.

I posted here some code that compares a std::function<> against a
virtual method call and some other alternatives. A function<>-object
adds only two ints and returns the result is about one nanosecond
on my Zen4-PC. That's not much.

[toc] | [prev] | [next] | [standalone]

#120368

On 26/09/2024 11:35, Bonita Montero wrote:
> Am 26.09.2024 um 10:29 schrieb David Brown:
> 
>> std::function<> can be very flexible, but it is often costly at run- 
>> time.  There are situations where the compiler can optimise away the 
>> overheads, but often at least some remains.
> 
> I posted here some code that compares a std::function<> against a
> virtual method call and some other alternatives. A function<>-object
> adds only two ints and returns the result is about one nanosecond
> on my Zen4-PC. That's not much.
> 

Please don't bother replying to posts unless you first read them, then 
think about them.  Otherwise you are just wasting everyone's time.

Nothing you write there contradicts what I wrote, or adds any new 
information.

[toc] | [prev] | [next] | [standalone]

#120371

Am 26.09.2024 um 13:27 schrieb David Brown:
^> Please don't bother replying to posts unless you first read them, then
> think about them.  Otherwise you are just wasting everyone's time.

I've read it and I'm thinking the overvhead of std::function<> ist
neglectable.

[toc] | [prev] | [next] | [standalone]

#120374

On Thu, 26 Sep 2024 13:31:22 +0200
Bonita Montero <Bonita.Montero@gmail.com> wrote:

> Am 26.09.2024 um 13:27 schrieb David Brown:
> ^> Please don't bother replying to posts unless you first read them,
> then
> > think about them.  Otherwise you are just wasting everyone's time.  
> 
> I've read it and I'm thinking the overvhead of std::function<> ist
> neglectable.
> 

As majority of things, it depends.
On CPU with deep OoO capabilities it likely depends on being on or off
critical latency path.
I'd guess that in your case std::function calls were off critical
latency path. In the other words, they were independent of each other.
In my measurements the calls were partially dependent which led to
higher cost - approximately 2ns both on Intel Skylake at 4.25 GHz and
on AMD Zen3 at 3.6 GHz.
Since in this algorithm call/return overhead is the main component
of the run time, 2ns addition was enough to make the whole test run
twice slower on Skylake and more than twice slower on Zen3.

[toc] | [prev] | [next] | [standalone]

#120375

Am 26.09.2024 um 14:25 schrieb Michael S:

> As majority of things, it depends.

I can also imagine code where the call-overhead might be relevant,
but the virtual dispatch on the function<>-object is that fast that
it is not relevant in 95% of all cases.

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.c++

csiph-web