On 09/26/2013 11:36 AM, Jakub Jelinek wrote:
> +struct gomp_task;
> struct gomp_taskgroup;
> +struct htab;
> +
> +struct gomp_task_depend_entry
> +{
> + void *addr;
> + struct gomp_task_depend_entry *next;
> + struct gomp_task_depend_entry *prev;
> + struct gomp_task *task;
> + bool is_in;
> + bool redundant;
> +};
I'm a bit confused about the combination of linked lists and reallocated
arrays. When did you decide to use what?
> + if ((flags & 8) && thr->task && thr->task->depend_hash)
> + {
> + struct gomp_task *parent = thr->task;
> + struct gomp_task_depend_entry elem, *ent = NULL;
> + size_t ndepend = (uintptr_t) depend[0];
> + size_t nout = (uintptr_t) depend[1];
> + size_t i;
> + gomp_mutex_lock (&team->task_lock);
> + for (i = 0; i < ndepend; i++)
> + {
> + elem.addr = depend[i + 2];
> + ent = htab_find (parent->depend_hash, &elem);
> + for (; ent; ent = ent->next)
> + if (i >= nout && ent->is_in)
> + continue;
> + else
> + break;
I wonder if we ought always defer tasks with dependencies and skip this lock
and search? Unless the taskgroup is truly weird, we *are* going to have
dependencies between the tasks. Dunno what exactly to do with final_tasks
that have unfulfilled dependencies...
I also think it would significantly clean up the code to declare a struct with
a variable tail for the depend argument. That would eliminate all of the
casting to uintptr_t and give names to the first two entries.
> + if (tsk->dependers == NULL)
> + {
> + tsk->dependers
> + = gomp_malloc (8 * sizeof (struct gomp_task *));
> + tsk->dependers[0]
> + = (struct gomp_task *) (uintptr_t) 1;
> + tsk->dependers[1]
> + = (struct gomp_task *) (uintptr_t) (8 - 2);
> + tsk->dependers[2] = task;
> + task->num_dependees++;
> + continue;
Another place for which a struct with variable tail would significantly clean
up the code. And here's where I wonder why you're using realloc'd arrays here
as opposed to another linked list?
Perhaps what we need are smaller linked list entries like
struct gomp_task_depend_node {
struct gomp_task *task;
struct gomp_task_depend_node *next;
struct gomp_task_depend_node *prev;
};
and a different hash table entry like
struct gomp_task_depend_head {
void *addr;
struct gomp_task_depend_node *outs;
struct gomp_task_depend_node *ins;
size_t n_ins;
};
If we scan the ndepend entries twice, we can find out how many nodes we need,
and allocate them with the task like you do now. Scanning the ndepends array
twice can be sped by only looking up the hash table entries once -- allocate a
local array of size ndepend entries and cache the lookups.
I'd say we don't need a count of the n_outs because all of them on the list
must be sequentially dependent. Thus any new task simply depends on the
previous task in the outs list. Thus imo it makes sense to have ins/outs point
to the tail of the list as opposed to the head.
Is is really worthwhile to detect redundant dependencies? It seems just as
easy to add multiple dependencies and let them just fall out naturally.
OTOH, perhaps you should just go ahead with this patch and we can evolve it
incrementally. I don't see anything technically wrong with it.
r~
