Changeset 57d677 in git


Ignore:
Timestamp:
Jan 8, 2014, 4:51:09 PM (10 years ago)
Author:
Andreas Steenpass <steenpass@…>
Branches:
(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')
Children:
6018f45ce4c19ecc818c5049efe3f94ad40c20db
Parents:
0463d5c11d6bcf715a2d7db36a4b48cd3174af48
git-author:
Andreas Steenpass <steenpass@mathematik.uni-kl.de>2014-01-08 16:51:09+01:00
git-committer:
Andreas Steenpass <steenpass@mathematik.uni-kl.de>2014-01-16 17:24:45+01:00
Message:
chg: update tasks.lib

Improve handling of internal data structures, especially intvecs.
(cherry picked from commit 091fbfe87825a276fac0079c772304a96a7cb118)

Signed-off-by: Andreas Steenpass <steenpass@mathematik.uni-kl.de>
File:
1 edited

Legend:

Unmodified
Added
Removed

  • Singular/LIB/tasks.lib

    r0463d5c r57d677  
    470470        // the number of local tasks with internal state 3 (result sent) or
    471471        // -1 (stopped)
    472     intvec queue = 0, 1..nlocaltasks, 0;   // zeroes for easier handling
     472    intvec queue = 1..nlocaltasks;
     473    int next = 1;
    473474
    474475    list links;
    … …  
    481482    int code;
    482483    int id;
    483     intvec demanded_tasks = 0, 0;   // zeroes for easier handling
     484    if (!defined(demanded_tasks)) {
     485        intvec demanded_tasks;
     486        int demanded_tasks_index = 1;
     487        exportto(Tasks, demanded_tasks);
     488        exportto(Tasks, demanded_tasks_index);
     489    }
     490    else {
     491        demanded_tasks = 0;
     492        demanded_tasks_index = 1;
     493    }
    484494    int ndemanded = -1;
    485495
    … …  
    489499
    490500    // auxiliary variables
     501    intvec waiting_tasks;
    491502    int wait;
    492503    int deadlock;
    493504    int tmp;
    494505    int i;
     506    int j;
    495507
    496508    while (nwaiting > 0) {
    … …  
    530542                write(links[nlinks],
    531543                    quote(startTasks_grandchild(
    532                     eval(localtasks[queue[2]].index), eval(pid_parent),
     544                    eval(localtasks[queue[next]].index), eval(pid_parent),
    533545                    eval(pid), eval(nlinks), eval(sem_write))));
    534                 assignment[queue[2]] = nlinks;
    535                 state[queue[2]] = 1;
     546                assignment[queue[next]] = nlinks;
     547                state[queue[next]] = 1;
    536548                nwaiting--;
    537                 queue = 0, queue[3..size(queue)];
     549                next++;
    538550            }
    539551            // wait == 0
    … …  
    544556                id = read(links[wait]);
    545557                state[id] = 2;
    546                 if (ndemanded > 0 && isElement(demanded_tasks, id)) {
     558                if (ndemanded > 0 && removeDemanded(id)) {
    547559                    write(links[wait], 1);
    548                     demanded_tasks = removeFromIntvec(demanded_tasks, id);
    549560                    ndemanded--;
    550561                    results_sent++;
    … …  
    558569                id = read(l(pid_parent));
    559570                if (state[id] == 0) {   // waiting
    560                     queue = removeFromIntvec(queue, id);
     571                    queue = give_priority(queue, intvec(id));
     572                    next++;
    561573                }
    562574                if (state[id] == 1 || state[id] == 2) {  // started or computed
    … …  
    565577                    write(links[assignment[id]],
    566578                        quote(startTasks_grandchild(
    567                         eval(localtasks[queue[2]].index), eval(pid_parent),
     579                        eval(localtasks[queue[next]].index), eval(pid_parent),
    568580                        eval(pid), eval(assignment[id]), eval(sem_write))));
    569                     assignment[queue[2]] = assignment[id];
     581                    assignment[queue[next]] = assignment[id];
    570582                    assignment[id] = 0;
    571                     state[queue[2]] = 1;
    572                     queue = 0, queue[3..size(queue)];
     583                    state[queue[next]] = 1;
     584                    next++;
    573585                }
    574586                // state[id] == -1 (stopped) or state[id] == 3 (sent)
    … …  
    580592            if (code == 1) {   // waitTasks
    581593                demanded_tasks = read(l(pid_parent));
     594                demanded_tasks_index = size(demanded_tasks);
    582595                ndemanded = read(l(pid_parent));
    583                 if (ndemanded > size(demanded_tasks)-2) {
    584                     ndemanded = size(demanded_tasks)-2;
    585                 }
    586                 if (demanded_tasks == 0:2 && ndemanded == -1) {
     596                if (ndemanded > demanded_tasks_index) {
     597                    ndemanded = demanded_tasks_index;
     598                }
     599                if (demanded_tasks == 0 && ndemanded == -1) {
    587600                    write(l(pid_parent), results_sent);
     601                    continue;
    588602                }
    589603                else {
    590604                    results_sent = 0;
    591605                }
     606                demanded_tasks = demanded_tasks[demanded_tasks_index..1];
    592607                deadlock = 0;
    593                 for (i = size(demanded_tasks)-1; i > 1; i--) {
     608                waiting_tasks = 0:demanded_tasks_index;
     609                j = 0;
     610                for (i = demanded_tasks_index; i > 0; i--) {
    594611                    id = demanded_tasks[i];
    595612                    if (state[id] == 0) {   // waiting
    596                         queue = give_priority(queue, id);
     613                        j++;
     614                        waiting_tasks[j] = id;
    597615                        deadlock = 1;
     616                    }
     617                }
     618                if (j > 0) {
     619                    waiting_tasks = waiting_tasks[1..j];
     620                    queue = queue[next..size(queue)];
     621                    next = 1;
     622                    queue = give_priority(queue, waiting_tasks);
     623                    waiting_tasks = 0;
     624                }
     625                for (i = demanded_tasks_index; i > 0; i--) {
     626                    id = demanded_tasks[i];
     627                    if (state[id] == 1) {   // started
     628                        deadlock = 0;
    598629                    }
    599630                    if (state[id] == 2) {   // computed
    600631                        write(links[assignment[id]], 1);
    601                         demanded_tasks = removeFromIntvec(demanded_tasks, id);
     632                        tmp = removeDemanded(id);
    602633                        ndemanded--;
    603634                        results_sent++;
    604                     }
    605                 }
    606                 for (i = size(demanded_tasks)-1; i > 1; i--) {
    607                     id = demanded_tasks[i];
    608                     if (state[id] == 1) {   // started
    609635                        deadlock = 0;
    610636                    }
    … …  
    618644                    write(links[nlinks],
    619645                        quote(startTasks_grandchild(
    620                         eval(localtasks[queue[2]].index), eval(pid_parent),
     646                        eval(localtasks[queue[next]].index), eval(pid_parent),
    621647                        eval(pid), eval(nlinks), eval(sem_write))));
    622                     assignment[queue[2]] = nlinks;
    623                     state[queue[2]] = 1;
     648                    assignment[queue[next]] = nlinks;
     649                    state[queue[next]] = 1;
    624650                    nwaiting--;
    625                     queue = 0, queue[3..size(queue)];
     651                    next++;
    626652                }
    627653            }
    … …  
    629655                id = read(l(pid_parent));
    630656                if (state[id] == 0) {   // waiting
    631                     queue = give_priority(queue, id);
     657                    queue = queue[next..size(queue)];
     658                    next = 1;
     659                    queue = give_priority(queue, intvec(id));
    632660                }
    633661                if (state[id] == 2) {   // computed
    … …  
    640668                write(links[assignment[id]],
    641669                    quote(startTasks_grandchild(
    642                     eval(localtasks[queue[2]].index), eval(pid_parent),
     670                    eval(localtasks[queue[next]].index), eval(pid_parent),
    643671                    eval(pid), eval(assignment[id]), eval(sem_write))));
    644                 assignment[queue[2]] = assignment[id];
     672                assignment[queue[next]] = assignment[id];
    645673                assignment[id] = 0;
    646                 state[queue[2]] = 1;
     674                state[queue[next]] = 1;
    647675                state[id] = 3;
    648676                nwaiting--;
    649677                nfinished++;
    650                 queue = 0, queue[3..size(queue)];
     678                next++;
    651679            }
    652680        }
    … …  
    659687                id = read(links[wait]);
    660688                state[id] = 2;
    661                 if (ndemanded > 0 && isElement(demanded_tasks, id)) {
     689                if (ndemanded > 0 && removeDemanded(id)) {
    662690                    write(links[wait], 1);
    663                     demanded_tasks = removeFromIntvec(demanded_tasks, id);
    664691                    ndemanded--;
    665692                    results_sent++;
    … …  
    687714            if (code == 1) {   // waitTasks
    688715                demanded_tasks = read(l(pid_parent));
     716                demanded_tasks_index = size(demanded_tasks);
    689717                ndemanded = read(l(pid_parent));
    690                 if (ndemanded > size(demanded_tasks)-2) {
    691                     ndemanded = size(demanded_tasks)-2;
    692                 }
    693                 if (demanded_tasks == 0:2 && ndemanded == -1) {
     718                if (ndemanded > demanded_tasks_index) {
     719                    ndemanded = demanded_tasks_index;
     720                }
     721                if (demanded_tasks == 0 && ndemanded == -1) {
    694722                    write(l(pid_parent), results_sent);
     723                    continue;
    695724                }
    696725                else {
    697726                    results_sent = 0;
    698727                }
    699                 for (i = size(demanded_tasks)-1; i > 1; i--) {
     728                demanded_tasks = demanded_tasks[demanded_tasks_index..1];
     729                for (i = demanded_tasks_index; i > 0; i--) {
    700730                    id = demanded_tasks[i];
    701731                    if (state[id] == 2) {   // computed
    702732                        write(links[assignment[id]], 1);
    703                         demanded_tasks = removeFromIntvec(demanded_tasks, id);
     733                        tmp = removeDemanded(id);
    704734                        ndemanded--;
    705735                        results_sent++;
    … …  
    752782}
    753783
    754 /* Check if n is an element of v[2..(size(v)-1)].
    755  * Note that v[1] and v[size(v)] are not checked.
     784/* Remove id from demanded_tasks and return 1, if id is an element of
     785 * demanded_tasks; return 0, otherwise. Note:
     786 * - demanded_tasks and demanded_tasks_index are (lib-)global objects
     787 *   exported in startTasks_child().
     788 * - demanded_tasks_index is used to avoid copying. It is defined to be
     789 *   the greatest integer with demanded_tasks[demanded_tasks_index] != 0
     790 *   and demanded_tasks[demanded_tasks_index+1] == 0 (if defined).
    756791 */
    757 static proc isElement(alias intvec v, alias int n)
    758 {
     792static proc removeDemanded(alias int id)
     793{
     794    if (demanded_tasks[demanded_tasks_index] == id) {
     795        demanded_tasks[demanded_tasks_index] = 0;
     796        demanded_tasks_index--;
     797        return(1);
     798    }
    759799    int i;
    760     for (i = size(v)-1; i > 1; i--) {
    761         if (v[i] == n) {
     800    for (i = demanded_tasks_index-1; i > 0; i--) {
     801        if (demanded_tasks[i] == id) {
     802            demanded_tasks[i..demanded_tasks_index]
     803                = demanded_tasks[(i+1)..demanded_tasks_index], 0;
     804            demanded_tasks_index--;
    762805            return(1);
    763806        }
    … …  
    766809}
    767810
    768 /* Remove the first occurence (if any) of n in v[2..(size(v)-1)].
    769  * Note that v[1] and v[size(v)] are not checked.
     811/* Move the elements in 'preferred' to the beginning of 'queue'. We may assume
     812 * that
     813 * - 'preferred' is a subset of 'queue';
     814 * - the elements of 'preferred' are distinct and non-zero;
     815 * - the elements of 'queue' are distinct and non-zero.
     816 * For performance reasons, we may also assume that 'queue' and 'preferred' are
     817 * more or less ordered in most cases. Note that queue has the format
     818 * '0, indices, 0'.
    770819 */
    771 static proc removeFromIntvec(intvec v, int n)
    772 {
    773     int size_v = size(v);
     820static proc give_priority(intvec queue, intvec preferred)
     821{
     822    int size_queue = size(queue);
     823    int size_preferred = size(preferred);
     824    if (size_queue == size_preferred) {
     825        return(queue);
     826    }
     827    int index = size_queue;
    774828    int i;
    775     for (i = size_v-1; i > 1; i--) {
    776         if (v[i] == n) {
    777             return(v[1..(i-1)], v[(i+1)..size_v]);
    778         }
    779     }
    780     return(v);
    781 }
    782 
    783 /* Move the first occurence (if any) of id in queue[2..(size(queue)-1)] to
    784  * queue[2]. Note that queue[1] and queue[size(v)] are not checked.
    785  */
    786 static proc give_priority(intvec queue, int id)
    787 {
    788     int size_queue = size(queue);
    789     int i;
    790     for (i = size_queue-1; i > 2; i--) {
    791         if (queue[i] == id) {
    792             return(0, id, queue[2..(i-1)], queue[(i+1)..size_queue]);
    793         }
    794     }
     829    int j;
     830    for (i = size_preferred; i > 0; i--) {
     831        for (j = size_queue; j > 0; j--) {
     832            if (queue[index] == preferred[i]) {
     833                queue[index] = 0;
     834                break;
     835            }
     836            index--;
     837            if (index == 0) {
     838                index = size_queue;
     839            }
     840        }
     841    }
     842    intvec not_preferred = 0:(size_queue-size_preferred);
     843    index = 1;
     844    for (i = 1; i <= size_queue; i++) {
     845        if (queue[i]) {
     846            not_preferred[index] = queue[i];
     847            index++;
     848        }
     849    }
     850    queue = preferred, not_preferred;
    795851    return(queue);
    796852}
    … …  
    921977            if (!sorted_in) {
    922978                requests[size(requests)+1] = list(tasks[T[i].index].linkID,
    923                     intvec(0, tasks[T[i].index].id),
     979                    intvec(tasks[T[i].index].id),
    924980                    tasks[T[i].index].links[2]);
    925981                links[size(links)+1] = tasks[T[i].index].links[1];
    … …  
    930986    /* send the reqests */
    931987    for (j = size(requests); j > 0; j--) {
    932         requests[j][2][size(requests[j][2])+1] = 0;
    933988        write(requests[j][3], 1);
    934989        write(requests[j][3], requests[j][2]);
    … …  
    9831038    for (j = size(requests); j > 0; j--) {
    9841039        write(requests[j][3], 1);
    985         write(requests[j][3], 0:2);
     1040        write(requests[j][3], 0);
    9861041        write(requests[j][3], -1);
    9871042    }
Note: See TracChangeset for help on using the changeset viewer.