habanero-rice / hclib

A C/C++ task-based programming model for shared memory and distributed parallel computing.
http://habanero-rice.github.io/hclib/
BSD 3-Clause "New" or "Revised" License
71 stars 35 forks source link

Deadlock example was creating redundant promises #48

Closed agrippa closed 7 years ago

agrippa commented 7 years ago

From what I can tell, promise objects were being created in the deadlock0 test which were not being used, leading to the code being confusing (correct me if I'm wrong). I've just made a small change to clean up that section of the code.

agrippa commented 7 years ago

Not to be reviewed/merged before #46

budimlic commented 7 years ago

This is true, the hclib_promise_create_n will create a promise and initialize promise_list[0] with it, then the test will later overwrite promise_list[0].

Why not use the hclib_promise_create_n call as it is right now, then just assign promise_list[0] to promise? Seems like the new code is duplicating the work done in hclib_promise_create_n

agrippa commented 7 years ago

Mostly because I think that hclib_promise_create_n is a confusing API so I was trying to minimize its usage. For example, I just realized after looking at it closer that this code was technically not creating redundant promises. By calling:

hclib_promise_create_n(1, true);

where 1 is a parameter called nb_promises and true is passed as a parameter called null_terminated, you would expect that it would create an array of length 2 with the first slot holding a promise and the second being NULL. Indeed, your comment indicates that's how you read it too.

In fact, all it does is allocate an array of length 1 and initialize the 0th slot to NULL. Which is incredibly counter-intuitive. Therefore, I would argue this is an improvement in readability.

budimlic commented 7 years ago

Yes, you are correct, hclib_promise_create_n(n,flag) creates an array of n promises, with the last one being NULL if the flag is set to true. That's really counterintuitive. But I think that's a topic for another pull request (create separate hclib_promise_create_n and hclib_promise_create_n_null_terminated).

I don't see a point in using an array of promises in this particular test, though. It's never used. Only the scalar promise variable is used in the test. So I suggest getting rid of the promise array completely.

DaoWen commented 7 years ago

One reason I used hclib_promise_create_n in this test was because it's not called in any of our other tests. If it's in the API, then we should use it. However, I don't see why we even have an option for not using the NULL terminator.

I agree the API is confusing (hence my screw-up here). I'd prefer removing the boolean argument, and always allocating n+1 slots, with the last slot always set to NULL.

In addition to the bug that Zoran pointed out, there's another bug in this test, which is also in the unpatched version: the future_list isn't NULL-terminated. The future pointers are the arguments that are actually passed into async_await, and that's what really needs to be NULL-terminated.

We assume internally that promise and future pointers can be directly cast back and forth, which means this must also work:

future_list = (hclib_future_t **) promise_list;

But that's a bit cryptic, so maybe we should add the following function to the C API:

static inline hclib_future_t **hclib_get_futures_for_promises(hclib_promise_t **promises) {
    HASSERT_STATIC(offsetof(hclib_promise_t, future) == 0, "Can't cast promise ptr to future ptr");
    return (hclib_future_t **) promises;
}

and use it like this:

future_list = hclib_get_futures_for_promises(promise_list);

Since promise_list is NULL-terminated, the resulting future_list is also correctly NULL-terminated.

agrippa commented 7 years ago

Just continuing the discussion here.

I can see two solutions to the hclib_promise_create_n issue:

  1. Simply change the behavior of hclib_promise_create_n to be more intuitive the way Nick suggested above. (always allocate n+1 slots, and always null terminate).
  2. Change the await APIs to take the number of futures as an additional argument, rather than using null termination to implicitly indicate the number of futures. This would make hclib_promise_create_n less necessary.

I've actually implemented the second option in a branch because I always found the null-termination semantics to be a bit confusing, subtle, and error prone. I'm also okay with the first option, but I'd like to hear what you guys think.

DaoWen commented 7 years ago

I'd prefer option 2 (the explicit count argument) because it's more flexible (e.g., you can await different sub-ranges of a single array in two different asyncs), and it would help internally in some places as well (e.g., we wouldn't need this hack). Obviously this will require some refactoring, but it's probably worth it.

budimlic commented 7 years ago

That's a very good point Nick. I like option 2 as well.