Coding: Fleeting Thoughts

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

Ben-oni
Posts: 278
Joined: Mon Sep 26, 2011 4:56 am UTC

Re: Coding: Fleeting Thoughts

Postby Ben-oni » Thu Aug 01, 2013 7:58 pm UTC

skeptical scientist wrote:Dynamic programming in python how-to:
  • Step 1: write a recursive function
  • Step 2: @memoize it
  • Step 3: profit

Correct. Dynamic programming is a "buzz word" for memoization.

When I was first reading about this fancy "dynamic programming" some years ago, I remember wondering what the fuss was about. After all, isn't that just functional programming with reasonable compiler optimizations turned on? Apparently I was just spoiled.

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Coding: Fleeting Thoughts

Postby EvanED » Thu Aug 01, 2013 9:27 pm UTC

That memoization can be considered a "reasonable optimization" even in situations where you can do it is, IMO, a gross overstatement. (And of course that ignores the fact that much of the time in the languages that people actually use, it's incorrect.) Memoization is almost a canonical example of a space/time tradeoff and there are significant memory effects that have to be considered, and that's not something that you likely want your optimizer doing for you in the general case IMO.

Besides, in terms of what's a buzzword, "dynamic programming" is an older term than "memoization." It would be more accurate to say that "memoization" is a buzzword for one way of performing dynamic programming. ("The term memoization was coined by Donald Michie in 1968" wikipedia. "The term dynamic programming was originally used in the 1940s by Richard Bellman... By 1953, he refined this to the modern meaning, referring specifically to nesting smaller decision problems inside larger decisions". wikipedia.)

Ben-oni
Posts: 278
Joined: Mon Sep 26, 2011 4:56 am UTC

Re: Coding: Fleeting Thoughts

Postby Ben-oni » Thu Aug 01, 2013 10:01 pm UTC

EvanED wrote:and that's not something that you likely want your optimizer doing for you in the general case IMO.

Unless, as I said, you turn it on.

EvanED wrote:Besides, in terms of what's a buzzword, "dynamic programming" is an older term than "memoization." It would be more accurate to say that "memoization" is a buzzword for one way of performing dynamic programming. ("The term memoization was coined by Donald Michie in 1968" wikipedia. "The term dynamic programming was originally used in the 1940s by Richard Bellman... By 1953, he refined this to the modern meaning, referring specifically to nesting smaller decision problems inside larger decisions". wikipedia.)

That... actually makes a lot more sense now. It sounds as though the meaning of the word "programming" in this context is similar to its meaning in the context of "linear programming". Which has nothing to do with "programming" in the context of this forum.

lalop
Posts: 210
Joined: Mon May 23, 2011 5:29 pm UTC

Re: Coding: Fleeting Thoughts

Postby lalop » Thu Aug 01, 2013 11:22 pm UTC

Hmm, knowing that dynamic programming is not a buzzword is, if anything, even worse than thinking that it was. Its name bears pretty much no resemblance to what it's doing. At least, before, I thought it was someone trying to be hip.

korona
Posts: 495
Joined: Sun Jul 04, 2010 8:40 pm UTC

Re: Coding: Fleeting Thoughts

Postby korona » Thu Aug 01, 2013 11:48 pm UTC

Ben-oni wrote:
EvanED wrote:and that's not something that you likely want your optimizer doing for you in the general case IMO.

Unless, as I said, you turn it on.

I don't think that there are good heuristics to decide which things should be memoized and which shouldn't. That is an incredibly hard task for compilers.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Coding: Fleeting Thoughts

Postby skeptical scientist » Fri Aug 02, 2013 2:57 am UTC

Memoization seems like it's mostly only useful in the case when it's being applied to a recursive function which is likely to call itself multiple times with the same argument. The classic example of this is the recursive fibonacci algorithm:

Code: Select all

def fib(n):
  if n < 2: return n
  return fib(n-1)+fib(n-2)

If you call fib(40), the recursion will cause fib(20) to be called 10946 times in the process of computing fib(40). Obviously, this is a huge waste of computational resources which would be resolved with a simple @memoize decorator. On my computer, fib(40) takes 48 seconds, but if it's declared with @memoize, it takes only .17 milliseconds. If I wanted to wait that long, fib(100) would take approximately 2 million years. With @memoize, it takes .45 milliseconds. This is perhaps not the best example of where memoization is useful, as there are better ways to compute the fibonacci sequence, but it is a very good example, and one of the simplest.

However, other than this particular sort of use, there's a good chance that memoization will waste more memory than it's worth for whatever speedup it creates. And I don't see how the compiler could really know whether memoization is going to be useful without knowing when, how many times, and with what arguments your function will be called. So I don't see how a compiler could consider it a reasonable optimization and do it automatically.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

korona
Posts: 495
Joined: Sun Jul 04, 2010 8:40 pm UTC

Re: Coding: Fleeting Thoughts

Postby korona » Fri Aug 02, 2013 12:37 pm UTC

So I'm writing a C++ application that makes heavy use of asynchronous callbacks. The code looks similar to JavaScript code written for node.js.
Some parts of the code look like this:

Code: Select all

Async::series(std::make_tuple(
   [=](std::function<void()> callback) {
      /* do some stuff, then call callback asynchronously */
   },
   [=](std::function<void()> callback) {
      /* do some stuff, then call callback asynchronously */
   },
   [=](std::function<void()> callback) {
      /* do some stuff, then call callback asynchronously */
   },
), [=]() { /* this is executed after all lambdas have been completed */ } );


Where the Async::series function executes the first lambda, passing it a callback that invokes the second lambda and so on. Thus all the lambdas are executed in sequence.

The problem with this code is that all lambdas take an argument of type std::function, i.e. a polymorphic function wrapper. Converting a lambda to an std::function object is slow. I'm thinking of ways to get rid of this polymorphic wrapper.

One solution would be to implemented this as a giant block of nested lambdas but I don't want to do that for obvious reasons.

Another solution would be to use a function object instead of a lambda that works like this:

Code: Select all

struct first_functor {
   template<typename Callback>
   struct real_functor {
      void operator() (first_functor &context, Callback callback) { /* do stuff here, then call callback */ };
   };
   /* some variables that real_functor::operator() needs */
};
struct second_functor { ... };

and then reimplement the Async::series function so that it takes a tuple of function objects, constructs the corresponding real_functor objects for the correct callback type and then invokes them.

I also don't want to do that because it would force me to write ugly function objects and do all capturing by hand. Does anyone have an idea for a nicer solution?

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Coding: Fleeting Thoughts

Postby EvanED » Fri Aug 02, 2013 2:50 pm UTC

Ben-oni wrote:
EvanED wrote:and that's not something that you likely want your optimizer doing for you in the general case IMO.

Unless, as I said, you turn it on.
As others have said, that depends on what you mean by "turn it on". If you say "the compiler should memoize when you do -O2" (which is how I interpreted your original statement)? No, I strongly disagree. If you say "the compiler should have a -fmemoize flag that turns on memoization"? No, still disagree.

If you mean "I've annotated f with a 'memoize' directive that tells the compiler to memoize f with some user-selectable cache sizing and expiration policy and annotated g with a different size and expiration policy", then yes, I agree. (Yes, there should be a default for those options, but if you can't override the default then it's not a "reasonable optimization" IMO.) Then again, I wouldn't really put that transformation under the purview of "the optimizer."

Edit
korona wrote:The problem with this code is that all lambdas take an argument of type std::function, i.e. a polymorphic function wrapper. Converting a lambda to an std::function object is slow.
What evidence do you have for this assertion? Do you have actual numbers, or are you just assuming?

User avatar
sparkyb
Posts: 1091
Joined: Thu Sep 06, 2007 7:30 pm UTC
Location: Camberville proper!
Contact:

Re: Coding: Fleeting Thoughts

Postby sparkyb » Sat Aug 03, 2013 3:38 am UTC

Confession: When I see someone using all sorts of advanced C++11 features, I can't decide if I should be jealous that I cannot take advantage of them because in my industry adoption of new language features is slow, or if I should be smug that they may think they're showing off using advanced features that most don't know yet, but really they are being impractical.

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 6577
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: Coding: Fleeting Thoughts

Postby Thesh » Sat Aug 03, 2013 3:45 am UTC

My experience with C# is that people like to use new features just to use new features, even in situations where the new features don't actually make the code more clean/clear or reduce code size. However, then you come across a legitimate usage for a feature that is so awesome and impressive that you get fired for masturbating at your desk.
Summum ius, summa iniuria.

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Coding: Fleeting Thoughts

Postby EvanED » Sat Aug 03, 2013 3:56 am UTC

I feel like sometimes it's really hard to tell. Like auto. In for (auto blah = mycontainer.begin()....) it's is definitely a good and legit use of auto that makes the code easier to read (if you can't use ranged-based for, like the restriction I put on myself for some stuff). But other times I just throw auto in there at other initializations, and I can't tell what the tradeoff is between explicitness and conciseness.

User avatar
sparkyb
Posts: 1091
Joined: Thu Sep 06, 2007 7:30 pm UTC
Location: Camberville proper!
Contact:

Re: Coding: Fleeting Thoughts

Postby sparkyb » Sat Aug 03, 2013 1:22 pm UTC

I'm all in favor of auto. In fact, I think my company is going to start to allow us to use auto. But when I see things like lambda I think "this is not C++".

korona
Posts: 495
Joined: Sun Jul 04, 2010 8:40 pm UTC

Re: Coding: Fleeting Thoughts

Postby korona » Sat Aug 03, 2013 6:26 pm UTC

Lambdas are just syntactic sugar making function objects easier to use. A lambda is compiled to something like

Code: Select all

struct some_unique_class_name {
   return_type operator() (/* arguments */) { /* code * };

   int a; /* captured variables */
   int b;

   some_unique_class_name(int a, int b) : a(a), b(b) { }
};

There is no magic involved. Not even virtual functions or memory allocation. Lambdas are as lightweight as non-virtual C functions (except when you capture types with heavyweight copy constructors). They do not really add anything you couldn't do before. Function objects are used extensively in the C++ standard library and nobody says "function objects are not C++".

EvanED wrote:What evidence do you have for this assertion? Do you have actual numbers, or are you just assuming?

For now I am just assuming, but I will do some benchmarks soon. I am assuming because converting a lambda to a std::function requires a dynamic memory allocation (the must be some memory to hold the captured variables) and a virtual method call to invoke it.

User avatar
Xeio
Friends, Faidites, Countrymen
Posts: 5101
Joined: Wed Jul 25, 2007 11:12 am UTC
Location: C:\Users\Xeio\
Contact:

Re: Coding: Fleeting Thoughts

Postby Xeio » Sat Aug 03, 2013 7:57 pm UTC

Thesh wrote:However, then you come across a legitimate usage for a feature that is so awesome and impressive that you get fired for masturbating at your desk.
So... async/await? :mrgreen:

User avatar
Yakk
Poster with most posts but no title.
Posts: 11127
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Coding: Fleeting Thoughts

Postby Yakk » Sun Aug 04, 2013 11:22 am UTC

Korona, why pass the next callback?

Instead take a `tuple` of `()->bool`, where `true` means continue, and have the harness call each element in turn.

It is a tad less flexible, but if you write a wrapper that turns such a `tuple` into a `()->bool` itself, you can build trees. Throw in a way to ignore the return value of on step (as easy as `(()->bool)->(()->true)`), and you can have "run after".
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

korona
Posts: 495
Joined: Sun Jul 04, 2010 8:40 pm UTC

Re: Coding: Fleeting Thoughts

Postby korona » Sun Aug 04, 2013 7:53 pm UTC

I have to pass the callback because the callback is not called when the function terminates but at some indeterminate time later. What I am doing is:

Code: Select all

[] (std::function<void()> callback) {
    /* ... */
    some_long_and_async_io_operation(fd, buffer, length, callback);
}

If the callback was called immediately when the function returns I wouldn't need distinct functions at all and I could just use normal procedural control flow.

User avatar
3fj
Posts: 1715
Joined: Wed Jun 11, 2008 1:13 pm UTC
Location: Land of Whisky and Bagpipes (LOWAB)
Contact:

Re: Coding: Fleeting Thoughts

Postby 3fj » Mon Aug 05, 2013 10:21 am UTC

Thesh wrote:My experience with C# is that people like to use new features just to use new features, even in situations where the new features don't actually make the code more clean/clear or reduce code size. However, then you come across a legitimate usage for a feature that is so awesome and impressive that you get fired for masturbating at your desk.

Well, I nearly got sacked for using inline predicate functions. Luckily I managed to clean myself up before my PM caught me, but sadly he was in no mood to learn new syntax and hated the idea. I still get calls from folk who are baffled by lambdas, which is odd because it's pretty standard. I call it old guys resting on their laurels, they call it writing complex code for no reason.
Everything's dead until it's alive. Man will exist, and then he will die. Just take the ride!

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 6577
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: Coding: Fleeting Thoughts

Postby Thesh » Mon Aug 05, 2013 10:33 am UTC

Yeah, people not learning syntax is not the same as dirty or complex. Lambdas can definitely be a nice way to reduce code size (and boilerplate!).
Summum ius, summa iniuria.

Dr. Willpower
Posts: 197
Joined: Wed May 28, 2008 3:55 pm UTC

Re: Coding: Fleeting Thoughts

Postby Dr. Willpower » Mon Aug 05, 2013 8:55 pm UTC

In reference to PHP woes from the previous page. Sometimes PHP can get murky. When I wrote this code it made sense to me, but when I look at it while editing this file I cringe.

Code: Select all

<?php
echo '<a href="index.php';
if ($CS->N < 1) echo '?comic=1';
else if (!$CS->isComic($CS->N + 1));
else echo '?comic='. ($CS->N + 1);
echo "\" title=\"Next comic!\">\n"; ?>
  <img src="pics/nextbutt.png" />
</a>
Image
Hat me, bro

bittyx
Posts: 194
Joined: Tue Sep 25, 2007 9:10 pm UTC
Location: Belgrade, Serbia

Re: Coding: Fleeting Thoughts

Postby bittyx » Mon Aug 05, 2013 9:30 pm UTC

Dr. Willpower wrote:In reference to PHP woes from the previous page. Sometimes PHP can get murky. When I wrote this code it made sense to me, but when I look at it while editing this file I cringe.

Code: Select all

<?php
echo '<a href="index.php';
if ($CS->N < 1) echo '?comic=1';
else if (!$CS->isComic($CS->N + 1));
else echo '?comic='. ($CS->N + 1);
echo "\" title=\"Next comic!\">\n"; ?>
  <img src="pics/nextbutt.png" />
</a>


Why don't you add a method to the class of your $CS object, something like getNextComic(), and handle most of the logic there? If it's a small project, you could even just make a method like getNextComicUrl(), which returns everything you need, and then just do:

Code: Select all

<a href="<?php echo $CS->getNextComicUrl(); ?>" title="Next comic!">
    <img src="pics/nextbutt.png">
</a>


Though a method like that would probably be a bad idea in any larger project (since it's very likely that it's not $CS's responsibility to know about URLs), you could gain a lot in terms of readability.

Also, add width, height, and alt attributes to your images - the first to help browsers render the page faster, while the last one helps accessibility and SEO.

Apart from that, it's *very* unreadable and confusing to write noops like that (I'm talking about that "else if" that ends in a semicolon). A slightly better version would be:

Code: Select all

<?php
    $href = 'index.php';
    if ($CS->N < 1)
    {
        $href .= '?comic=1';
    }
    else if ($CS->isComic($CS->N + 1))
    {
        $href .= '?comic=' . ($CS->N + 1);
    }
?>
<a href="<?php echo $href; ?>" title="Next comic!">
    <img src="pics/nextbutt.png">
</a>


Finally, pay attention to indentation - it's probably one of the most important factors of readable code. There are various popular indent styles, but the most important thing is to be consistent, and use the same style within a project.

User avatar
Xeio
Friends, Faidites, Countrymen
Posts: 5101
Joined: Wed Jul 25, 2007 11:12 am UTC
Location: C:\Users\Xeio\
Contact:

Re: Coding: Fleeting Thoughts

Postby Xeio » Mon Aug 05, 2013 9:30 pm UTC

Dr. Willpower wrote:When I wrote this code it made sense to me, but when I look at it while editing this file I cringe.
Yes, it is pretty horrible to save 2 characters by abbreviating button to butt.

Dr. Willpower
Posts: 197
Joined: Wed May 28, 2008 3:55 pm UTC

Re: Coding: Fleeting Thoughts

Postby Dr. Willpower » Tue Aug 06, 2013 3:18 am UTC

bittyx wrote:...


I appreciate your help. This file is not part of a big project. Nor will anyone else ever lay eyes on the PHP.

Xeio wrote:Yes, it is pretty horrible to save 2 characters by abbreviating button to butt.


Yeah, the abbreviation is just to include the word butt on the page.
Image
Hat me, bro

User avatar
Xenomortis
Not actually a special flower.
Posts: 1447
Joined: Thu Oct 11, 2012 8:47 am UTC

Re: Coding: Fleeting Thoughts

Postby Xenomortis » Wed Aug 07, 2013 12:19 pm UTC

I've just found a For-Case construct in our code base.
I'm curious as to the chain of events that lead to this.
Image

User avatar
PM 2Ring
Posts: 3713
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

Re: Coding: Fleeting Thoughts

Postby PM 2Ring » Wed Aug 07, 2013 5:00 pm UTC

Xenomortis wrote:I've just found a For-Case construct in our code base.
I'm curious as to the chain of events that lead to this.

Is that like Duff's device?

User avatar
Xanthir
My HERO!!!
Posts: 5408
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Coding: Fleeting Thoughts

Postby Xanthir » Wed Aug 07, 2013 5:02 pm UTC

No, Duff's device actually uses the case for a reason - you can enter it at any point. Standard For-Case is always entered at the start, and just proceeds linearly.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Yakk
Poster with most posts but no title.
Posts: 11127
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Coding: Fleeting Thoughts

Postby Yakk » Wed Aug 07, 2013 5:41 pm UTC

korona wrote:I have to pass the callback because the callback is not called when the function terminates but at some indeterminate time later. What I am doing is:

Code: Select all

[] (std::function<void()> callback) {
    /* ... */
    some_long_and_async_io_operation(fd, buffer, length, callback);
}

If the callback was called immediately when the function returns I wouldn't need distinct functions at all and I could just use normal procedural control flow.

Have your functions return std::future<void>, or some other way to signal "async process finished, proceed to next step".

Or even have your functions *block* and return only when done: if you are doing this in a task thread, having that task thread block isn't all *that* expensive.

You could write "async chain", where you take a series of possibly blocking operations, and tie them together into an asynchronous chain that, when invoked, returns a std::future to the last operation's return value. But really, this is just a bog standard blocking chain that terminates with an async-like launching of the entire chain.

Or are you so short threads that you cannot afford to have one store the execution state of your chain as execution state?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
Xenomortis
Not actually a special flower.
Posts: 1447
Joined: Thu Oct 11, 2012 8:47 am UTC

Re: Coding: Fleeting Thoughts

Postby Xenomortis » Wed Aug 07, 2013 6:38 pm UTC

PM 2Ring wrote:
Xenomortis wrote:I've just found a For-Case construct in our code base.
I'm curious as to the chain of events that lead to this.

Is that like Duff's device?


VB because that's what we use at work:
Spoiler:

Code: Select all

For i as Integer = 1 to 5
    Select Case i
        Case 1
            ....
        Case 2
            ....
        Case 3
            ....
        Case 4
            ....
        Case 5
            ....
    End Select
Next

It's not like this got that way through refactoring either; looking through the SVN log shows that it was written this way from the start.

I would be surprised if any of my colleagues know about Duff's Device.
Image

User avatar
PM 2Ring
Posts: 3713
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

Re: Coding: Fleeting Thoughts

Postby PM 2Ring » Wed Aug 07, 2013 6:57 pm UTC

Xenomortis wrote:VB because that's what we use at work:
Spoiler:

Code: Select all

For i as Integer = 1 to 5
    Select Case i
        Case 1
            ....
        Case 2
            ....
        Case 3
            ....
        Case 4
            ....
        Case 5
            ....
    End Select
Next

It's not like this got that way through refactoring either; looking through the SVN log shows that it was written this way from the start.

Oh, God. That's awful!

Xenomortis wrote:I would be surprised if any of my colleagues know about Duff's Device.

Fair enough. I don't know VB, but I guess it would be impossible to do Duff's Device in VB, since it needs drop-through cases, and the ability to jump into the middle of a do loop. And for that matter, I expect a lot of younger C/C++ programmers would never have seen Duff's Device, either. It's not exactly the kind of coding style that's encouraged. Even Tom Duff himself said:
Disgusting, no? But it compiles and runs just fine. I feel a combination of pride and revulsion at this discovery. If no one's thought of it before, I think I'll name it after myself.

It amazes me that after 10 years of writing C there are still little corners that I haven't explored fully. (Actually, I have another revolting way to use switches to implement interrupt driven state machines but it's too horrid to go into.)
Many people (even bwk?) have said that the worst feature of C is that switches don't break automatically before each case label. This code forms some sort of argument in that debate, but I'm not sure whether it's for or against.

:)

User avatar
Xenomortis
Not actually a special flower.
Posts: 1447
Joined: Thu Oct 11, 2012 8:47 am UTC

Re: Coding: Fleeting Thoughts

Postby Xenomortis » Wed Aug 07, 2013 7:16 pm UTC

PM 2Ring wrote:Oh, God. That's awful!

I wouldn't have minded so much if the loop variable started at 0. :wink:

PM 2Ring wrote:Fair enough. I don't know VB, but I guess it would be impossible to do Duff's Device in VB, since it needs drop-through cases, and the ability to jump into the middle of a do loop. And for that matter, I expect a lot of younger C/C++ programmers would never have seen Duff's Device, either. It's not exactly the kind of coding style that's encouraged.

VB (.NET anyway) allows jumps into the middle of a loops and switches. But it doesn't have fall through.
Neither does C#, even though that still requires an explicit "break;" statement.
Image

korona
Posts: 495
Joined: Sun Jul 04, 2010 8:40 pm UTC

Re: Coding: Fleeting Thoughts

Postby korona » Wed Aug 07, 2013 8:44 pm UTC

Yakk wrote:
korona wrote:I have to pass the callback because the callback is not called when the function terminates but at some indeterminate time later. What I am doing is:

Code: Select all

[] (std::function<void()> callback) {
    /* ... */
    some_long_and_async_io_operation(fd, buffer, length, callback);
}

If the callback was called immediately when the function returns I wouldn't need distinct functions at all and I could just use normal procedural control flow.

Have your functions return std::future<void>, or some other way to signal "async process finished, proceed to next step".

Or even have your functions *block* and return only when done: if you are doing this in a task thread, having that task thread block isn't all *that* expensive.

You could write "async chain", where you take a series of possibly blocking operations, and tie them together into an asynchronous chain that, when invoked, returns a std::future to the last operation's return value. But really, this is just a bog standard blocking chain that terminates with an async-like launching of the entire chain.

Or are you so short threads that you cannot afford to have one store the execution state of your chain as execution state?

The problem is that thousands or ten thousands of those operations may be running simultaneously, so I cannot create a stack/thread for each. The problem with std::future is that it doesn't have a async wait method. (std::future is designed to work with threads and I try to avoid threads in this application)

I will benchmark various alternatives for std::function and post the results in a few days. I guess I can implement a specialized version of std::function that does not do memory allocation and only uses a single call through a function-pointer if I restrict myself to "small" functors e.g. lambdas that only capture a single word. gcc should be able to completely inline the call in this case.

EDIT: inline-able std::function like behavior is indeed possible. Here is the code:

Code: Select all

#include <cstdint>
#include <cstdio>
#include <new>

template<typename F>
class function;

template<typename R, typename ... A>
class function<R(A...)> {
public:
   template<typename T>
   function(const T &functor) {
      static_assert(sizeof(T) <= sizeof(uintptr_t), "Functor too large");
      p_intern<T> *ptr = new (&p_words) p_intern<T>(functor);
      p_functor_helper = &p_intern<T>::invoke;
   }

   R operator() (A... args) {
      return p_functor_helper(&p_words, args...);
   }

private:
   template<typename T>
   struct p_intern {
      T p_real_functor;
      
      p_intern(const T &functor) : p_real_functor(functor) { }
      
      static R invoke(void *ptr, A... args) {
         p_intern<T> *self = reinterpret_cast<p_intern<T>*>(ptr);
         return self->p_real_functor(args...);
      }
   };

   uintptr_t p_words;
   R (*p_functor_helper)(void *, A...);
};

int main() {
   int i = 41;
   function<int(int)> f([i] (int x) { return i + x; });
   printf("%d is the answer\n", f(1));
}


which gcc compiles to:

Code: Select all

.LC0:
   .string   "%d is the answer\n"
main:
   subq   $8, %rsp
   movl   $42, %esi
   movl   $.LC0, %edi
   xorl   %eax, %eax
   call   printf
   xorl   %eax, %eax
   addq   $8, %rsp
   ret


EDIT2: libstdc++'s std::function implementation is NOT able to inline the call in this case.
Last edited by korona on Wed Aug 07, 2013 9:59 pm UTC, edited 3 times in total.

jazz14456
Posts: 58
Joined: Thu Jul 04, 2013 9:04 pm UTC
Location: New Netherlands

Re: Coding: Fleeting Thoughts

Postby jazz14456 » Wed Aug 07, 2013 9:31 pm UTC

M.qrius wrote:

Code: Select all

boolean ever = true;
for(;ever;) {
    [Do stuff]
}


Nice way to write down an eternal loop :P


In Objective-C its simply

while (1){
}

:P
This place is ending and its time to go.

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Coding: Fleeting Thoughts

Postby EvanED » Wed Aug 07, 2013 10:18 pm UTC

You know that while(1) {} works in any of the C family languages, right? (Actually at present I've come to favor for(;;) as it won't lead to a conditional-expression-is-constant warning.)

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 6577
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: Coding: Fleeting Thoughts

Postby Thesh » Wed Aug 07, 2013 10:59 pm UTC

I prefer:

Code: Select all

loop_start:

//code

goto loop_start;
Summum ius, summa iniuria.

User avatar
3fj
Posts: 1715
Joined: Wed Jun 11, 2008 1:13 pm UTC
Location: Land of Whisky and Bagpipes (LOWAB)
Contact:

Re: Coding: Fleeting Thoughts

Postby 3fj » Thu Aug 08, 2013 1:13 pm UTC

EvanED wrote:You know that while(1) {} works in any of the C family languages, right? (Actually at present I've come to favor for(;;) as it won't lead to a conditional-expression-is-constant warning.)

I do it that way because that's the way I was taught loops in the first place. It was "for(;;) loops forever because it's dumb and you haven't told it to do anything clever." before going on to explain the initialisation;specifier;incrementer parts.

I have a phone interview on Monday, and I was told to go brush up on basic principles that I'm going to get questioned on. Now, I understand why they are looking at basic technical competency here, but does anyone actually do something with inheritance and say "Look at me doing all this sweet inheritance!"? I feel like the only time I study these concepts is for these basic interviews because they're so ingrained in what we do regularly that you no longer think about it in such a compartmentalised fashion.
Everything's dead until it's alive. Man will exist, and then he will die. Just take the ride!

User avatar
Yakk
Poster with most posts but no title.
Posts: 11127
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Coding: Fleeting Thoughts

Postby Yakk » Thu Aug 08, 2013 2:50 pm UTC

korona wrote:
Yakk wrote:
korona wrote:I have to pass the callback because the callback is not called when the function terminates but at some indeterminate time later. What I am doing is:

Code: Select all

[] (std::function<void()> callback) {
    /* ... */
    some_long_and_async_io_operation(fd, buffer, length, callback);
}

If the callback was called immediately when the function returns I wouldn't need distinct functions at all and I could just use normal procedural control flow.

Have your functions return std::future<void>, or some other way to signal "async process finished, proceed to next step".

Or even have your functions *block* and return only when done: if you are doing this in a task thread, having that task thread block isn't all *that* expensive.

You could write "async chain", where you take a series of possibly blocking operations, and tie them together into an asynchronous chain that, when invoked, returns a std::future to the last operation's return value. But really, this is just a bog standard blocking chain that terminates with an async-like launching of the entire chain.

Or are you so short threads that you cannot afford to have one store the execution state of your chain as execution state?

The problem is that thousands or ten thousands of those operations may be running simultaneously, so I cannot create a stack/thread for each.

Ah, you are "so starved for threads that you cannot store execution state as executation state".

I'd still attempt to move the "next method" as far out of being run explicitly, and into the framework. Can you reliably get a "something to wait on" handle from the things you are doing that you can multiple-wait on?

Because then I'd have functions that return "something to wait on" to chain, and I'd chain them in the framework instead of inside the function the way you are doing it.

EDIT: inline-able std::function like behavior is indeed possible. Here is the code:

How is that inlining? It still has to cross a function pointer, there is no practical way to inline that in many contexts.

Regardless, google up on C++ delegates -- you can write a class that wraps "this plus member pointer" slickly. It is on that website with the orange blocks I think. It doesn't do memory allocation.

You could also do std::function-with-a-size that does inplace new replacing your implicit size of pointer-sized. Alignment might also be key. Your implementation also misses the possibility of operator= or construction being non-trivial (such as move optimizations), as well. I'd at least do some static_asserts that these are not "in play", and that your inplace construct has enough room, etc.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

korona
Posts: 495
Joined: Sun Jul 04, 2010 8:40 pm UTC

Re: Coding: Fleeting Thoughts

Postby korona » Thu Aug 08, 2013 3:38 pm UTC

Yakk wrote:Because then I'd have functions that return "something to wait on" to chain, and I'd chain them in the framework instead of inside the function the way you are doing it.

That might indeed be possible, but I fear that it would further complicate the control flow as I do not only have "this operation is complete" callbacks but also "here is the data you requested" callbacks.

Yakk wrote:
EDIT: inline-able std::function like behavior is indeed possible. Here is the code:

How is that inlining? It still has to cross a function pointer, there is no practical way to inline that in many contexts.

Regardless, google up on C++ delegates -- you can write a class that wraps "this plus member pointer" slickly. It is on that website with the orange blocks I think. It doesn't do memory allocation.

You could also do std::function-with-a-size that does inplace new replacing your implicit size of pointer-sized. Alignment might also be key. Your implementation also misses the possibility of operator= or construction being non-trivial (such as move optimizations), as well. I'd at least do some static_asserts that these are not "in play", and that your inplace construct has enough room, etc.

Yeah, it does cross a function pointer but the example I posted shows that the gcc's constant propagation optimizations are strong enough to inline that code in easy cases. In fact I always pass a static lambda to the callback and never a function pointer so I'm always in an "easy case".

I already have a static assert to check if the functor is too large in the code I posted. I added other static asserts to check for non-trivial copy constructors, assignment operators and destructors. As you said, the functor size can be configured to an arbitrary value by replacing uintptr_t with another type.

User avatar
PM 2Ring
Posts: 3713
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

Re: Coding: Fleeting Thoughts

Postby PM 2Ring » Thu Aug 08, 2013 4:08 pm UTC

EvanED wrote:You know that while(1) {} works in any of the C family languages, right? (Actually at present I've come to favor for(;;) as it won't lead to a conditional-expression-is-constant warning.)


One of the Amiga system headers had

Code: Select all

#define FOREVER for(;;)

but I never bothered to use it in my own code, preferring to write it out explicitly when I needed an infinite loop (which was pretty often in Amiga GUI code).

User avatar
phlip
Restorer of Worlds
Posts: 7572
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Coding: Fleeting Thoughts

Postby phlip » Fri Aug 09, 2013 3:30 am UTC

I've heard stories of

Code: Select all

#define ever ;;
for essentially the same reason.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
sparkyb
Posts: 1091
Joined: Thu Sep 06, 2007 7:30 pm UTC
Location: Camberville proper!
Contact:

Re: Coding: Fleeting Thoughts

Postby sparkyb » Sat Aug 10, 2013 3:40 pm UTC

phlip wrote:

Code: Select all

#define ever ;;

That thing where you want to use a certain name as a variable or function/method and some other jerk has defined it as a macro so even scoping and namespaces won't save you. Please don't define words that could easily be used in other contexts as macros. I had a problem recently where my DrawText method stopped working after including someone else's header that through some chain (I could never track down) included winuser.h which had #define DrawText DrawTextA. Thanks Microsoft.

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Coding: Fleeting Thoughts

Postby EvanED » Sat Aug 10, 2013 6:46 pm UTC

sparkyb wrote:
phlip wrote:

Code: Select all

#define ever ;;

That thing where you want to use a certain name as a variable or function/method and some other jerk has defined it as a macro so even scoping and namespaces won't save you. Please don't define words that could easily be used in other contexts as macros. I had a problem recently where my DrawText method stopped working after including someone else's header that through some chain (I could never track down) included winuser.h which had #define DrawText DrawTextA. Thanks Microsoft.

My personal style is that an identifier is a preprocessor macro if and only if it is all capital letters.

So even something like const double PI = 3.14; is no good, because it's not a preprocessor macro. Probably overkill, but I've been burned too many times by macro conflicting with things that aren't macros.


Return to “Coding”

Who is online

Users browsing this forum: Xanthir and 4 guests