From d146dbbab184a6e78f58bda9f997d68bac34b240 Mon Sep 17 00:00:00 2001 From: Holden Rohrer Date: Tue, 14 Jan 2020 21:05:59 -0500 Subject: moved exclusions to responder --- examples/jarvis.js | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) diff --git a/examples/jarvis.js b/examples/jarvis.js index 0df6151..157808f 100644 --- a/examples/jarvis.js +++ b/examples/jarvis.js @@ -138,10 +138,8 @@ var search = new Space(); search.adhoc('jarvis'); // The search space is the word jarvis, so whenever that's caught, a relevant function can be called. var read = new Search(search); var expire = {}; -var limits = []; // an array of senders within the last 5 seconds to act as a 'rate limiter' function detectPrompt(send, tiles, locs){ // tries to detect the prompt ('jarvis') and calls respond if found. - if (limits.indexOf(send) >= 0) return; for (let i=0; i 0) respond(results); + if (results.length > 0) respond(results, send); expire[loc] = setTimeout(() => {read.del(loc); delete expire[loc];}, 30000); } limits.push(send); - setTimeout(() => {limits.splice(limits.indexOf(send))}, 5*1000); } let response = new Space(); response.adhoc('yes, my liege'); -function respond(coord){ +var limits = []; // an array of senders within the last 5 seconds to act as a 'rate limiter' +function respond(coord, send){ + if (limits.indexOf(send) >= 0) return; console.log('called at', coord); callct += 1; response.loc = coord; writes.enqueue(response.towrite().concat(notifRefresh())); read.update(response); + setTimeout(() => {limits.splice(limits.indexOf(send))}, 5*1000); } -- cgit From 8d4ea0bb9cdda4021c54ed564382b89ddec8c800 Mon Sep 17 00:00:00 2001 From: Holden Rohrer Date: Thu, 16 Jan 2020 23:21:15 -0500 Subject: added explanation for schedule architecture --- architecture | 21 +++++++++++++++++++++ 1 file changed, 21 insertions(+) create mode 100644 architecture diff --git a/architecture b/architecture new file mode 100644 index 0000000..c161699 --- /dev/null +++ b/architecture @@ -0,0 +1,21 @@ +Say you have several queues A, B, ... +Each queue has a length K_n. +Each queue has a weight K_w. K_w adjusted such that \sumK_w=1 +If k items are requested, a set of items from the tops of each relevant queue will be returned. +K_c <= K_n items were chosen from queue K. +Minimize \sum|kK_w-K_c|. << Jesus Christ that's it. How could I be so stupid. + +main(queueList, num) -> while (not have num) getNumOrAll(queueList[top], remaining) + +getNumOrAll(queue, num): + Step 1: Make array of num*job.weight + Step 2: "Remove" all num%1 from array, and count + Step 3: "Sort" array by num. + Step 4: Continue counting. Subtract one from each array member until at num. +^^ Not perfect + 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). + Step 2.5: If empty, remove prio && jobs[prio]; return. + 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. -- cgit 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 --- architecture | 21 ----------- tools/schedule.js | 102 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 102 insertions(+), 21 deletions(-) delete mode 100644 architecture create mode 100644 tools/schedule.js diff --git a/architecture b/architecture deleted file mode 100644 index c161699..0000000 --- a/architecture +++ /dev/null @@ -1,21 +0,0 @@ -Say you have several queues A, B, ... -Each queue has a length K_n. -Each queue has a weight K_w. K_w adjusted such that \sumK_w=1 -If k items are requested, a set of items from the tops of each relevant queue will be returned. -K_c <= K_n items were chosen from queue K. -Minimize \sum|kK_w-K_c|. << Jesus Christ that's it. How could I be so stupid. - -main(queueList, num) -> while (not have num) getNumOrAll(queueList[top], remaining) - -getNumOrAll(queue, num): - Step 1: Make array of num*job.weight - Step 2: "Remove" all num%1 from array, and count - Step 3: "Sort" array by num. - Step 4: Continue counting. Subtract one from each array member until at num. -^^ Not perfect - 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). - Step 2.5: If empty, remove prio && jobs[prio]; return. - 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. 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(-) 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(-) 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(-) 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 2cc02e19410ea9a97a76480d84e0dc3be0efe312 Mon Sep 17 00:00:00 2001 From: Holden Rohrer Date: Sat, 18 Jan 2020 08:40:38 -0500 Subject: moved jarvis to schedule --- examples/jarvis.js | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/examples/jarvis.js b/examples/jarvis.js index 157808f..14bbaf7 100644 --- a/examples/jarvis.js +++ b/examples/jarvis.js @@ -7,7 +7,7 @@ const ms = require('../utils/measurespace'); const vec = require('../utils/vec'); const comb = require('../utils/comb'); const Search = require('../tools/search'); -const Queue = require('../tools/queue'); +const sched = require('../tools/schedule'); const ri = require('../utils/rectintersect'); //// Basic handling on open and close of the socket @@ -78,7 +78,7 @@ function tileHandler(send, source, tiles){ } //// "userspace" functions for responses, like to tileUpdates -var writes = new Queue(1000, 200, (elems) => main.write(elems)); +var writes = new sched.Queue(1000, 200, (elems) => main.write(elems)); var command = 'jarvis' var sig = 'feynmansfedora' -- 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(-) 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(-) 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