From f71719631dd793f39e6c629314fd81a4c06c19d2 Mon Sep 17 00:00:00 2001 From: Holden Rohrer Date: Fri, 17 Jan 2020 00:32:53 -0500 Subject: finally made schedule.js --- tools/schedule.js | 102 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 102 insertions(+) create mode 100644 tools/schedule.js (limited to 'tools') diff --git a/tools/schedule.js b/tools/schedule.js new file mode 100644 index 0000000..02dc883 --- /dev/null +++ b/tools/schedule.js @@ -0,0 +1,102 @@ +// A mixed paradigm scheduler + +// The core managed data type: a queue will be pushed a number of these and asked to manage it. +function Job(data, prio=0, wt=1){ + // Data is an array; + // Ideally, Both prio and wt are functions which take one argument: how many write cycles they've been waiting. This helps manage time-sensitive jobs. + // But this is too computationally difficult, so they are integer constants. + + // Immutable Properties + this.data = data; //A set of work to be done (like character writes) + this.prio = prio; // If a.prio > b.prio, all of `a.data` will be sent before any of `b.data` + this.wt = wt; // After numerous calls, (amount called of a/amount called of b) = a.wt/b.wt if a.prio = b.prio + this.maxr = data.length/wt; // A utility calculation: If a job has a lower maxr, it will run out of data earlier. + + // Mutable Properties + this.wacc = 0; // mutable property: Queue will change this to keep track between dequeues of how much "left over" push real estate this should have. + this.start; // The write # this job was introduced on. Also for Queue use. +} + +function Queue(maxExport, call, delay){ + // Every delay ms, Queue executes `call(maxExport # of objs in queue)` + let jobs = {}; // Links priorities to unordered arrays of jobs + let prios = []; // Array of priorities (keys of jobs), sorted. + let open = false; + let disab = true; + let writes = 0; + + this.enqueue = function(job){ + job.start = writes; + let prio = job.prio; + if (!jobs[prio]) jobs[prio] = []; + jobs[prio].splice(0, Math.abs(bs(jobs[prio], job, (el, ne) => el.maxr - ne.maxr)), job); + push(job); + prios.splice(0, Math.abs(bs(prios, prio, (el, ne) => el-ne)), prio) + if (open) dequeue(); + } + + this.enable = function(){ + disab = false; + if (open) dequeue(); + } + + this.disable = function(){ + disab = true; + } + + function dequeue(){ + if (disab){ + open = true; + return; + } + if (prios.length == 0){ + open = true; + return; + } + open = false; + let data = []; + while (data.length < maxExport){ + data.push(...getNumOrAll(prios[prios.length-1]), maxExport-data.length); + } + + writes++; + call(data); + setTimeout(dequeue, delayms); + } + + function getNumOrAll(prio, num){ + /* + + Step 1: (Pre-)sort by job.data.length/job.weight. + Step 2: Start at lowest, and pop all until job.data.length>job.normweight*num (decreasing num as popping and recalc job.normweight). Delete the job. + Step 3: Then, pop job.normweight*num//1 elems from remaining, without num decrease or normweight recalc. But keep job.wacc = job.normweight*num%1 + Step 4: Shallow copy job array, and sort by job.wacc. + Step 5: Iterate through array (high->low), and subtract 1 until the length of output is num. + Step 6: If empty, remove prio && jobs[prio]; return. + */ + let jobq = jobs[prio]; + let dequeued = []; + let weightsum = Math.sum(jobq.map(job => job.wt)).reduce((acc, cur)=>acc+cur); + while (job[0].data.length<(job[0].wacc+job[0].wt*num/weightsum)){ + weightsum -= job.wt; + dequeued.push(...jobq.shift().data); + } + for (job of jobq){ + job.wacc += job.wt*num/weightsum; + let data = job.data; + let topop = job.wacc-job.wacc%1; + job.wacc -= topop + dequeued.push(...data.splice(-topop)); + } + for (job of jobq.splice().sort((el, ne) => el.wacc-ne.wacc)){ + if (dequeued.length == num) break; + job.wacc--; + dequeue.push(job.pop()); + } + if (jobq.length == 0){ + delete jobs[prio]; + prios.splice(bs(prios, prio, (el, ne)=>el-ne), 1); + } + return dequeued; + } +} -- cgit From 870d834c5d20d67820d68d94e345ed7e6a66af9e Mon Sep 17 00:00:00 2001 From: Holden Rohrer Date: Fri, 17 Jan 2020 00:35:37 -0500 Subject: removed extraneous writes var and added comments --- tools/schedule.js | 8 ++------ 1 file changed, 2 insertions(+), 6 deletions(-) (limited to 'tools') diff --git a/tools/schedule.js b/tools/schedule.js index 02dc883..7778ed8 100644 --- a/tools/schedule.js +++ b/tools/schedule.js @@ -14,19 +14,16 @@ function Job(data, prio=0, wt=1){ // Mutable Properties this.wacc = 0; // mutable property: Queue will change this to keep track between dequeues of how much "left over" push real estate this should have. - this.start; // The write # this job was introduced on. Also for Queue use. } function Queue(maxExport, call, delay){ // Every delay ms, Queue executes `call(maxExport # of objs in queue)` let jobs = {}; // Links priorities to unordered arrays of jobs let prios = []; // Array of priorities (keys of jobs), sorted. - let open = false; - let disab = true; - let writes = 0; + let open = true; // Is dequeue() allowed to be called (i.e., has the timeout expired?) + let disab = true; // Is the queue disabled? this.enqueue = function(job){ - job.start = writes; let prio = job.prio; if (!jobs[prio]) jobs[prio] = []; jobs[prio].splice(0, Math.abs(bs(jobs[prio], job, (el, ne) => el.maxr - ne.maxr)), job); @@ -59,7 +56,6 @@ function Queue(maxExport, call, delay){ data.push(...getNumOrAll(prios[prios.length-1]), maxExport-data.length); } - writes++; call(data); setTimeout(dequeue, delayms); } -- cgit From 7e32677b7d61d84cf9b67133f9a12d37523120ba Mon Sep 17 00:00:00 2001 From: Holden Rohrer Date: Fri, 17 Jan 2020 00:36:23 -0500 Subject: typo in tools/schedule.js --- tools/schedule.js | 1 - 1 file changed, 1 deletion(-) (limited to 'tools') diff --git a/tools/schedule.js b/tools/schedule.js index 7778ed8..399b8e4 100644 --- a/tools/schedule.js +++ b/tools/schedule.js @@ -27,7 +27,6 @@ function Queue(maxExport, call, delay){ let prio = job.prio; if (!jobs[prio]) jobs[prio] = []; jobs[prio].splice(0, Math.abs(bs(jobs[prio], job, (el, ne) => el.maxr - ne.maxr)), job); - push(job); prios.splice(0, Math.abs(bs(prios, prio, (el, ne) => el-ne)), prio) if (open) dequeue(); } -- cgit From 32615549686567094ce80d89ad33695acfafa3ef Mon Sep 17 00:00:00 2001 From: Holden Rohrer Date: Fri, 17 Jan 2020 00:44:11 -0500 Subject: reorg comments in tools/schedule.js --- tools/schedule.js | 24 ++++++++++++++---------- 1 file changed, 14 insertions(+), 10 deletions(-) (limited to 'tools') diff --git a/tools/schedule.js b/tools/schedule.js index 399b8e4..83d7853 100644 --- a/tools/schedule.js +++ b/tools/schedule.js @@ -27,7 +27,8 @@ function Queue(maxExport, call, delay){ let prio = job.prio; if (!jobs[prio]) jobs[prio] = []; jobs[prio].splice(0, Math.abs(bs(jobs[prio], job, (el, ne) => el.maxr - ne.maxr)), job); - prios.splice(0, Math.abs(bs(prios, prio, (el, ne) => el-ne)), prio) + prios.splice(0, Math.abs(bs(prios, prio, (el, ne) => el-ne)), prio); // prios is meant to be sorted least to most, and each job layer is too (by "maximum number of rounds"). + // These were sorted like this so that getNumOrAll could use [0] or [.length-1] or .pop instead of having to re-sort lists repetitively. if (open) dequeue(); } @@ -41,6 +42,7 @@ function Queue(maxExport, call, delay){ } function dequeue(){ + // Wraps getNumOrAll, managing open/disab, and concatenating possibly multiple layers if (disab){ open = true; return; @@ -60,22 +62,18 @@ function Queue(maxExport, call, delay){ } function getNumOrAll(prio, num){ - /* - - Step 1: (Pre-)sort by job.data.length/job.weight. - Step 2: Start at lowest, and pop all until job.data.length>job.normweight*num (decreasing num as popping and recalc job.normweight). Delete the job. - Step 3: Then, pop job.normweight*num//1 elems from remaining, without num decrease or normweight recalc. But keep job.wacc = job.normweight*num%1 - Step 4: Shallow copy job array, and sort by job.wacc. - Step 5: Iterate through array (high->low), and subtract 1 until the length of output is num. - Step 6: If empty, remove prio && jobs[prio]; return. - */ + // Step 1: (Pre-)sort by job.data.length/job.weight. let jobq = jobs[prio]; let dequeued = []; + + // Step 2: Start at lowest, and pop all until job.data.length>job.normweight*num (decreasing num as popping and recalc job.normweight). Delete the job. let weightsum = Math.sum(jobq.map(job => job.wt)).reduce((acc, cur)=>acc+cur); while (job[0].data.length<(job[0].wacc+job[0].wt*num/weightsum)){ weightsum -= job.wt; dequeued.push(...jobq.shift().data); } + + // Step 3: Then, pop job.normweight*num//1 elems from remaining, without num decrease or normweight recalc. But keep job.wacc = job.normweight*num%1 for (job of jobq){ job.wacc += job.wt*num/weightsum; let data = job.data; @@ -83,15 +81,21 @@ function Queue(maxExport, call, delay){ job.wacc -= topop dequeued.push(...data.splice(-topop)); } + + // Step 4: Shallow copy job array, and sort by job.wacc. for (job of jobq.splice().sort((el, ne) => el.wacc-ne.wacc)){ + // Step 5: Iterate through array (high->low), and subtract 1 until the length of output is num. if (dequeued.length == num) break; job.wacc--; dequeue.push(job.pop()); } + + // Step 6: If empty, remove prio && jobs[prio]; return. if (jobq.length == 0){ delete jobs[prio]; prios.splice(bs(prios, prio, (el, ne)=>el-ne), 1); } + return dequeued; } } -- cgit From e8ebf9ec7639a95ddf1a0a61a7a4996a570e261a Mon Sep 17 00:00:00 2001 From: Holden Rohrer Date: Sat, 18 Jan 2020 08:44:01 -0500 Subject: queue-compat and bugfix in schedule.js---calls from jarvis still don't work --- tools/schedule.js | 18 +++++++++++------- 1 file changed, 11 insertions(+), 7 deletions(-) (limited to 'tools') diff --git a/tools/schedule.js b/tools/schedule.js index 83d7853..18278f0 100644 --- a/tools/schedule.js +++ b/tools/schedule.js @@ -1,7 +1,11 @@ // A mixed paradigm scheduler +// RECOMMENDED: Adjust maxr with each round, unless this is determined to be potentially circumventable (maybe maxr ranks remain constant as long as they are recalc on insertion---so function-style?) + +const bs = require('binary-search'); + // The core managed data type: a queue will be pushed a number of these and asked to manage it. -function Job(data, prio=0, wt=1){ +exports.Job = function(data, prio=0, wt=1){ // Data is an array; // Ideally, Both prio and wt are functions which take one argument: how many write cycles they've been waiting. This helps manage time-sensitive jobs. // But this is too computationally difficult, so they are integer constants. @@ -16,7 +20,7 @@ function Job(data, prio=0, wt=1){ this.wacc = 0; // mutable property: Queue will change this to keep track between dequeues of how much "left over" push real estate this should have. } -function Queue(maxExport, call, delay){ +exports.Queue = function(delayms, maxExport, call){ // Every delay ms, Queue executes `call(maxExport # of objs in queue)` let jobs = {}; // Links priorities to unordered arrays of jobs let prios = []; // Array of priorities (keys of jobs), sorted. @@ -24,6 +28,7 @@ function Queue(maxExport, call, delay){ let disab = true; // Is the queue disabled? this.enqueue = function(job){ + if (! (job instanceof exports.Job)) job = new exports.Job(job); let prio = job.prio; if (!jobs[prio]) jobs[prio] = []; jobs[prio].splice(0, Math.abs(bs(jobs[prio], job, (el, ne) => el.maxr - ne.maxr)), job); @@ -53,10 +58,9 @@ function Queue(maxExport, call, delay){ } open = false; let data = []; - while (data.length < maxExport){ - data.push(...getNumOrAll(prios[prios.length-1]), maxExport-data.length); + while (prios.length > 0 && data.length < maxExport){ + data.push(...getNumOrAll(prios[prios.length-1], maxExport-data.length)); } - call(data); setTimeout(dequeue, delayms); } @@ -67,8 +71,8 @@ function Queue(maxExport, call, delay){ let dequeued = []; // Step 2: Start at lowest, and pop all until job.data.length>job.normweight*num (decreasing num as popping and recalc job.normweight). Delete the job. - let weightsum = Math.sum(jobq.map(job => job.wt)).reduce((acc, cur)=>acc+cur); - while (job[0].data.length<(job[0].wacc+job[0].wt*num/weightsum)){ + let weightsum = jobq.map(job => job.wt).reduce((acc, cur)=>acc+cur); + while (jobq[0] && jobq[0].data.length<(jobq[0].wacc+jobq[0].wt*num/weightsum)){ weightsum -= job.wt; dequeued.push(...jobq.shift().data); } -- cgit From 7386e7324aed533e28b26e666525a036e6dac47a Mon Sep 17 00:00:00 2001 From: Holden Rohrer Date: Sat, 18 Jan 2020 15:46:15 -0500 Subject: Implemented bug fix for maxr in schedule.js Rankings may have been messed up because as new insertions get added, the data.length changes per write. --- tools/schedule.js | 6 ++---- 1 file changed, 2 insertions(+), 4 deletions(-) (limited to 'tools') diff --git a/tools/schedule.js b/tools/schedule.js index 18278f0..033fddb 100644 --- a/tools/schedule.js +++ b/tools/schedule.js @@ -1,7 +1,5 @@ // A mixed paradigm scheduler -// RECOMMENDED: Adjust maxr with each round, unless this is determined to be potentially circumventable (maybe maxr ranks remain constant as long as they are recalc on insertion---so function-style?) - const bs = require('binary-search'); // The core managed data type: a queue will be pushed a number of these and asked to manage it. @@ -14,7 +12,7 @@ exports.Job = function(data, prio=0, wt=1){ this.data = data; //A set of work to be done (like character writes) this.prio = prio; // If a.prio > b.prio, all of `a.data` will be sent before any of `b.data` this.wt = wt; // After numerous calls, (amount called of a/amount called of b) = a.wt/b.wt if a.prio = b.prio - this.maxr = data.length/wt; // A utility calculation: If a job has a lower maxr, it will run out of data earlier. + this.maxr = () => this.data.length/this.wt; // A utility calculation: If a job has a lower maxr, it will run out of data earlier. // Mutable Properties this.wacc = 0; // mutable property: Queue will change this to keep track between dequeues of how much "left over" push real estate this should have. @@ -31,7 +29,7 @@ exports.Queue = function(delayms, maxExport, call){ if (! (job instanceof exports.Job)) job = new exports.Job(job); let prio = job.prio; if (!jobs[prio]) jobs[prio] = []; - jobs[prio].splice(0, Math.abs(bs(jobs[prio], job, (el, ne) => el.maxr - ne.maxr)), job); + jobs[prio].splice(0, Math.abs(bs(jobs[prio], job, (el, ne) => el.maxr() - ne.maxr())), job); prios.splice(0, Math.abs(bs(prios, prio, (el, ne) => el-ne)), prio); // prios is meant to be sorted least to most, and each job layer is too (by "maximum number of rounds"). // These were sorted like this so that getNumOrAll could use [0] or [.length-1] or .pop instead of having to re-sort lists repetitively. if (open) dequeue(); -- cgit