Page 249 of 250

Re: Coding: Fleeting Thoughts

Posted: Sun Feb 10, 2019 4:08 pm UTC
by Yakk
Why would commits take 5 minutes?!

Re: Coding: Fleeting Thoughts

Posted: Sun Feb 10, 2019 4:26 pm UTC
by commodorejohn
Yakk wrote:Why would commits take 5 minutes?!

Obviously, because you're in a hurry and would rather they take five seconds. This is the way of things.

Re: Coding: Fleeting Thoughts

Posted: Sun Feb 10, 2019 6:58 pm UTC
by Xenomortis
I suspect something other than ~500 line text files are being committed...

Re: Coding: Fleeting Thoughts

Posted: Sun Feb 10, 2019 7:48 pm UTC
by Flumble
Yakk wrote:Why would commits take 5 minutes?!

Fine, it was closer to 3 minutes each. I thought it was a good idea to archive the xkcraftia backups in a git repository (since it's the default version control these days), thinking "oh, git can handle binary blobs well enough". Alas, it takes significantly longer to perform a commit than to copy the whole directory and the commit is significantly larger than storing a copy.
Note that these were commits for which nearly everything changed. (especially after the update to minecraft 1.13 in which every single piece of the world was repackaged)

Now borg was only twice as fast with committing a backup, but it did manage to de-duplicate a bunch of data so the end result is slightly smaller than separate backups.
Of course today's backup is be 'small' in both borg and git because less than a tenth of the files have changed, but now I've got borg set up so screw (g)it.

Re: Coding: Fleeting Thoughts

Posted: Mon Feb 11, 2019 9:13 pm UTC
by Yakk
"oh, git can handle binary blobs well enough"


Hahahahahahahahahaahahahahahahahaha

ahum.

Re: Coding: Fleeting Thoughts

Posted: Mon Feb 25, 2019 5:12 pm UTC
by Flumble

Code: Select all

...
kmlReq.addEventListener('load', () => {
   const routes = toGeoJSON.kml(kmlReq.responseXML)
   const features = routes.features.map(({'geometry': g, 'properties': { 'name': n='' }}) => ({'name': n, 'geom': g})) //flatten the structure a bunch
   const [points,paths] = features.partition(({'geom': {'type': t}}) => t == 'Point') //Array.prototype.partition should be included in ES2020
...


ECMAScript is starting to look like a proper language what with arrow functions, destructuring, imports and template literals. Now all it needs is a super-strict mode (no side-effects allowed), a good type system and a lazy runtime. :mrgreen:

Xanthir, since you're the standards guy around here, should I use quotes around object keys? Should I use on<x> rather than addEventListener for all eventing? Should I use semicolons to end statements?

Re: Coding: Fleeting Thoughts

Posted: Mon Feb 25, 2019 7:28 pm UTC
by Xanthir
Flumble wrote:
Xanthir, since you're the standards guy around here, should I use quotes around object keys?

No, it's just a few unnecessary characters. Unless you're writing JSON, in which case it's required.

Should I use on<x> rather than addEventListener for all eventing?

Feel free to for small examples, but since only one source can use the onFoo attribute at a time, using aEL is always the more reliable method. We've been looking for a while at finally adding a .on() API that makes slightly better choices for events anyway.

Should I use semicolons to end statements?

Yes. No-semicolon people are the devil.

Re: Coding: Fleeting Thoughts

Posted: Mon Feb 25, 2019 8:46 pm UTC
by Soupspoon
I agree;

Re: Coding: Fleeting Thoughts

Posted: Tue Feb 26, 2019 12:00 am UTC
by Flumble
Tanks for the answers. :)
Xanthir wrote:Yes. No-semicolon people are the devil.

In my defence, most of the stuff I write unambiguously continues a statement at the end of a line (with a binop or opening brackets) or ends a statement on the next line (with a keyword).


Unrelated thought: I've recently looked into the Assignment Problem and "implemented" (copy+paste another implementation and change the syntax to match the target language) the hungarian method in a new language, because it promised to be O(n^3) and was easy enough to move (and vaguely understand) the code.
But the assignment problem can be expressed in a linear program (link because I keep forgetting the specifics) and linear programs can be solved in O(n^2.5) these days. So I wonder if I should just use a general solver in the future.
Will a solution always have 1s and 0s for all worker-job pairings? (assuming I throw in some variation in the weights so you don't end up with e.g. two workers with exactly the same weights so putting 0.3 and 0.7 worker on a job is a valid solution)

Re: Coding: Fleeting Thoughts

Posted: Tue Feb 26, 2019 1:01 pm UTC
by Tub
Flumble wrote:

Code: Select all

...
kmlReq.addEventListener('load', () => {
   const routes = toGeoJSON.kml(kmlReq.responseXML)
   const features = routes.features.map(({'geometry': g, 'properties': { 'name': n='' }}) => ({'name': n, 'geom': g})) //flatten the structure a bunch
   const [points,paths] = features.partition(({'geom': {'type': t}}) => t == 'Point') //Array.prototype.partition should be included in ES2020
...

Using an arrow function means that you can't use 'this' to refer to kmlReq in the callback. Refering to kmlReq is going to lead to fun things if you ever decide to load multiple shapefiles and refactor that thing into a loop, or you're re-using kmlReq for a second request further down the function.

Flumble wrote:Xanthir, since you're the standards guy around here, should I use quotes around object keys?

Are you using or planning on using the closure compiler? If you are, then quotes have a special meaning: unquoted property names may be minified, quoted property names may not.

(The ability to mangle property names puts the closure compiler way ahead of any other minifier I know, but the hassle of distinguishing between minifiable and non-minifiable property names is often more work than it's worth.)

Otherwise, I usually omit the quotes because it's less typing and it looks better with my current syntax highlighting when they're not string-coloured. :roll:

Flumble wrote:Should I use semicolons to end statements?

To elaborate on Xanthirs answer, automatic semicolon insertion is the devil. Unfortunately, placing semicolons doesn't help against its evils, nor can it be disabled.

It bears repeating that one of the following pieces of code is different than the others. If you can't spot which and why, then you need to install a linter and start placing semicolons today.

Code: Select all

return {
  a: 42
}

Code: Select all

return
{ a: 42 }

Code: Select all

return { a:
42 }


Flumble wrote:[..]hungarian method in a new language, because it promised to be O(n^3)
[..]
[..]linear programs can be solved in O(n^2.5) these days.

Aside from the issue that (binary) integer programming has different complexities than linear programming: tell me, what does the n refer to in both of these formulas?

Re: Coding: Fleeting Thoughts

Posted: Tue Feb 26, 2019 2:50 pm UTC
by Flumble
Tub wrote:Using an arrow function means that you can't use 'this' to refer to kmlReq in the callback. Refering to kmlReq is going to lead to fun things if you ever decide to load multiple shapefiles and refactor that thing into a loop, or you're re-using kmlReq for a second request further down the function.

Of course if I'd refactor it to a loop it would look like

Code: Select all

for (const addr of addresses) {
   const req = new XMLHttpRequest()
   req.addEventListener('load', () => somethingWith(req))
   ...
}

There's no funny business with all the reqs being one and the same reference despite being block-scoped. At least there wasn't with for (const v of [1,2,3]) {const w = v; setTimeout(()=>console.log(w), 50*v)}.

Tub wrote:Otherwise, I usually omit the quotes because it's less typing and it looks better with my current syntax highlighting when they're not string-coloured. :roll:

My highlighter (Atom) is behaving really weird (an identifier is in order of precedence: green in a const declaration or if it's a single capital, yellow if it's a CSS prop or HTML attr name and has a dot on the left side, orange if it has an opening paren, purple if it has a dot on either side, or grey), so only quotes make them stand out. But the thing about possibly minifying sounds like a good enough reason not to do it. It's not like it makes a difference for the parser or makes it more/less valid JSON anyway.

Re: ASI
Spoiler:

Code: Select all

return ; //<- inserted here
{ a: 42 } ; //<-and here

Yeah I came across that too when advocating my non-use of semicolons. Opening-bracket-on-the-same-line styles save the day once more. :lol:


Tub wrote:
Flumble wrote:[..]hungarian method in a new language, because it promised to be O(n^3)
[..]
[..]linear programs can be solved in O(n^2.5) these days.

[..]tell me, what does the n refer to in both of these formulas?

Hmm, for the hungarian method n≈max(workers,jobs) ⇒ O(n^3) and an LP encoding is n≈workers*jobs ⇒ O(n^5). Why do you ask? :roll:
(does binary optimization have a better algorithm than real-valued optimization?)

Re: Coding: Fleeting Thoughts

Posted: Tue Feb 26, 2019 3:03 pm UTC
by Xanthir
Tub wrote:
Using an arrow function means that you can't use 'this' to refer to kmlReq in the callback.


...huh. I never knew that aEL passed the object you registered the event on via 'this'. Interesting.

Refering to kmlReq is going to lead to fun things if you ever decide to load multiple shapefiles and refactor that thing into a loop


Specifically, Tubs is referring to the following common problem:

Code: Select all

for(var i = 0; i < 5; i++) {
  setTimeout(()=>alert(i), 50);
}


Immediately after running, you'll get five alerts, all of which say "5". This is because all the functions grabbed the *same* variable binding to i, which was mutated in place by the loop, so at the end i is set to 5 and they all see that.

The solution to this used to be annoying, but luckily it's pretty trivial these days. If what you're looping over is iterable, you can just use a for-of loop and it works automatically:

Code: Select all

for(var el of list) {
  setTimeout(()=>alert(el.name), 50);
}


Alternately you can just introduce another, block-scoped variable (using the "let" or "const" keywords instead of "var") inside the loop and have the functions use that instead:

Code: Select all

for(var i = 0; i < 5; i++) {
  const j = i;
  setTimeout(()=>alert(j), 50);
}


Both of these work because you get a brand new binding of the variable on each iteration, so each function is seeing totally separate variables.

Re: Coding: Fleeting Thoughts

Posted: Tue Feb 26, 2019 3:35 pm UTC
by Flumble
Xanthir wrote:Alternately you can just introduce another, block-scoped variable (using the "let" or "const" keywords instead of "var") inside the loop and have the functions use that instead:

You don't even need to introduce an alias; just stop using var (which binds the variable to the whole function scope so it exists after your loop is done) altogether:

Code: Select all

for(let i = 0; i < 5; i++) {
  setTimeout(()=>alert(i), 50);
}


[edit]Well, it still makes no sense that the i in the arrow gets/is a different binding for each iteration as pointed out below. But hey, it automagically works the way you want it to.

Re: Coding: Fleeting Thoughts

Posted: Tue Feb 26, 2019 5:43 pm UTC
by Xanthir
Ah! I didn't realize that plain-for would establish the correct binding scopes for block-scoped variables! That's exciting!

Re: Coding: Fleeting Thoughts

Posted: Tue Feb 26, 2019 10:50 pm UTC
by Tub
Flumble wrote:

Code: Select all

return ; //<- inserted here
{ a: 42 } ; //<-and here

Yeah I came across that too when advocating my non-use of semicolons. Opening-bracket-on-the-same-line styles save the day once more. :lol:

Interesting that you got it wrong, then. Hint: that's not an object literal there. I predict you're going to learn about one more arcane JavaScript feature today :lol:

Another valid answer to the your question of quoting property names is that you should always quote them to turn this silent unexpected behaviour into a syntax error.

Flumble wrote:(does binary optimization have a better algorithm than real-valued optimization?)

The fundamental theorem of linear programming only holds for continuous variables. As soon as you go discrete, bad things happen to your complexity.

Xanthir wrote:you can just use a for-of loop and it works automatically:

Code: Select all

for(var el of list) {
  setTimeout(()=>alert(el.name), 50);
}

I tested that, it will also output the last element repeatedly. Further research says that let and const and their block level scopes do all the magic; for-of does nothing relevant.

(I'm glad we talked about this; yesterday I totally would have gotten some of these wrong!)

Re: Coding: Fleeting Thoughts

Posted: Wed Feb 27, 2019 1:03 am UTC
by Xanthir
...dangit, I definitely *meant* to type "let" in that example, too.

Yeah, "var" is the thing that breaks stuff. But *also*, it's not just the let/const keyword doing the work; it's important that the for-of loop is specified to create a particular (non-obvious, non-trivial) set of binding scopes that causes it to work correctly. I wasn't aware that plain-for would do the same scope stuff.

Re: Coding: Fleeting Thoughts

Posted: Wed Feb 27, 2019 1:20 am UTC
by phlip
Flumble wrote:
You don't even need to introduce an alias; just stop using var (which binds the variable to the whole function scope so it exists after your loop is done) altogether:

Code: Select all

for(let i = 0; i < 5; i++) {
  setTimeout(()=>alert(i), 50);
}

... there must be some deep magic going on there to let you use "i++" in the loop statement and yet have the "i"s in separate loop iterations be different variables for the closures...

Re: Coding: Fleeting Thoughts

Posted: Wed Feb 27, 2019 1:49 am UTC
by Xanthir
Aha, indeed: https://noraesae.net/2017/09/14/lexical ... -for-loop/

It examines what bindings are formed by the initializer, then generates a succession of nested binding scopes establishes new variables of the same name, initialized with the value of the previous binding scope's version of the variable at the end of the loop! *Then* it executes the incrementor on the newly created inner scope variable.

Re: Coding: Fleeting Thoughts

Posted: Wed Feb 27, 2019 10:44 am UTC
by Tub
So the tl;dr is that let/const are not just scoping restrictions, but the runtime will actually create a new variable each time program flow encounters a let/const declaration for capturing purposes. Hence, implementing let/const requires more than resolving naming conflicts, enforcing temporal dead zones and preventing const assignments. It's impossible to emulate let/const using var with a simple compiler pass, and babel'ing some of todays examples exhibits interesting workarounds.

'for' loops have additional logic such that any variable declared in the initialization will also be considered a new variable each loop. Thinking about it, they have to be, if you want something like

Code: Select all

for (const i of [1,2,3])

to work.

None of this will prevent you from modifying the variable after capturing. This one still prints a bunch of nulls:

Code: Select all

for (let i of [1,2,3]) {
    setTimeout(()=>console.log(i), 100);
    i = null;
}


It's unfortunate that the MDN article on let mentions nothing of this.

Re: Coding: Fleeting Thoughts

Posted: Wed Feb 27, 2019 12:49 pm UTC
by Flumble
Tub wrote:Hint: that's not an object literal there.

whyyyyyy.jpg
whyyyyyy.jpg (29.16 KiB) Viewed 6756 times

It kind of makes sense that javascript would prefer parsing it as a block rather than an expression statement. But labels must not exist outside of assembler languages.

But wait! There's more:

Code: Select all

()=>{
   return
   {a: 42, u: 1337} // Syntax error at the second colon
}

Shouldn't an object literal be a valid expression statement? Why isn't the parser retrying it as an expression? :?


phlip wrote:... there must be some deep magic going on there to let you use "i++" in the loop statement and yet have the "i"s in separate loop iterations be different variables for the closures...

I think the javascript gods smiled, since it does work exactly the way you want it to. :mrgreen:

Re: Coding: Fleeting Thoughts

Posted: Wed Feb 27, 2019 1:17 pm UTC
by phlip
Flumble wrote:
Shouldn't an object literal be a valid expression statement? Why isn't the parser retrying it as an expression? :?

I dunno, I prefer the simplicity of "when we see an open brace, if we're expecting a statement, it's a block, if we're expecting an expression, it's an object"... sure, it's still not as clear as if we weren't overloading the characters in the first place, but at least it's simple and consistent.

Anyway, you can always force the issue by wrapping it parens:

Code: Select all

return
({a: 5}) // is parsed as an object literal
// (still isn't actually returned, though)

Spoiler:
(btw if you've ever seen that "wat" presentation... y'know, the one with:

Code: Select all

>>> [] + []

>>> [] + {}
[object Object]
>>> {} + []
0
>>> {} + {}
NaN
then this whole thing is, like, a third of the answer to what's going on there...)

Re: Coding: Fleeting Thoughts

Posted: Wed Feb 27, 2019 3:17 pm UTC
by DavidSh
Flumble wrote:Unrelated thought: I've recently looked into the Assignment Problem and "implemented" (copy+paste another implementation and change the syntax to match the target language) the hungarian method in a new language, because it promised to be O(n^3) and was easy enough to move (and vaguely understand) the code.
But the assignment problem can be expressed in a linear program (link because I keep forgetting the specifics) and linear programs can be solved in O(n^2.5) these days. So I wonder if I should just use a general solver in the future.
Will a solution always have 1s and 0s for all worker-job pairings? (assuming I throw in some variation in the weights so you don't end up with e.g. two workers with exactly the same weights so putting 0.3 and 0.7 worker on a job is a valid solution)


The assignment problem, formulated as a linear program in the natural way, is a member of the class for which, barring ties, optimal solutions to the linear program have all integer values. Basically, all relevant submatrices of the constraint matrix have determinants in {0, +1, -1}.

Re: Coding: Fleeting Thoughts

Posted: Wed Mar 06, 2019 10:41 pm UTC
by Flumble
I have a web page with a bunch of iframes in them (because I think that's the best way to show multiple pages side by side) all on the same domain, but I want to go back and forth in history in each frame independently. Unfortunately all frames push history to a global stack, so window.history.back() goes back in whichever frame last opened a page regardless of which frame made the function call.

Assuming there is a workaround, what's the least hacky way to accomplish it? (StackOverflow is a mess on this subject)

Re: Coding: Fleeting Thoughts

Posted: Thu Mar 07, 2019 3:41 am UTC
by Tub
frames are just windows. Isn't there something like myIframe.contentWindow.history.back() ?

Re: Coding: Fleeting Thoughts

Posted: Sat Mar 23, 2019 7:24 pm UTC
by operator[]

Code: Select all

(^|[^/]\*/)[^/]*(/[^*][^/]*)*([^:\"'\(*]|^)//([^;\"'\)\{\}\n]*\n[ \t]*[^ \t\}]|[^;\"'\)\n]*;[^;\n)]*;[^\{\}]*(\n|$))

Guess the regex!

Spoiler:
It searches for (non-commented out, not within string, not containing {}) //-style comments in CSS, which would break if that was actually parsed as a comment.

Backstory: I read Xanthir's post on Single Line Comments (//) in CSS a while back, which states that a large problem with adding single-line comments to CSS is that minifiers would cause single-line comments to comment out a whole stylesheet. That seems true enough; it's not a big problem for newly developed sites, which could just update their minifiers, but existing sites might already contain instances of // and break. But it made me wonder, what would happen if you changed the parsing rule for // comments to stop the comment at the first occurrence of { or }, or to revert back to the current parsing of // when a brace is encountered within the comment? It's a terrible hack, even by web standards, by it would make // comments in minified stylesheets mostly harmless, and for non-minified sheets it might be fine because it preserves author intent better.

So I wrote a regex that searches for instances of // that would change behavior, ran it on the 3 million most visited pages from webarchive (takes about 40 seconds using GCP BigQuery), and checked for affected elements on the found pages using Selenium. Turns out, about ~1% of all sites are affected, and in 5-10% of those cases, it affects front page styling (mostly minor padding changes).

I imagine that's too much breakage to propose making CSS support such comments, even if the {} parsing rule was palatable... but it was certainly a fun data mining exercise.

(Raw data, including example breakage. #-style comments break roughly as much content, while ///-style ones break 5-10 times less.)

Re: Coding: Fleeting Thoughts

Posted: Fri Mar 29, 2019 7:02 am UTC
by gd1
A prototype that makes no sense: Pototrype or Pototripe.

Cops and Robbers program

Code: Select all

#include <iostream>

using namespace std;

int main()
{
   bool got_you;
   
   cout << "*!* *!*" << endl;
   
   got_you = true;
   cout << "The value stored in got_you is: " << got_you << endl;
   
   while(1)
   {
      If(got_you=true)
      {
         cout << "Nuh uh." << endl;
         got_you = false;
         cout << "The value stored in got_you is: " << got_you << endl;
      }
      Else
      {
         cout << "Ya huh." << endl;
         got_you = true;
         cout << "The value stored in got_you is: " << got_you << endl;
      }
   }
   
   return 0;
}

Re: Coding: Fleeting Thoughts

Posted: Thu Apr 11, 2019 2:43 pm UTC
by Tub
I really wish javascript's Map class had the ability to accept multiple keys.

With the good old object-as-maps, you'd just concatenate all your keys; they had to be strings anyway.

Code: Select all

let m = {};
m[x + '|' + y] = 42.

Somewhat expensive if you want to implement huge multi-dimensional arrays, but fine for smaller collections, as long as your keys can be stringified.

With the new Map, you can use arbitrary types and objects as keys, but object equality checks whether they're the same object, not whether they're equal.

Code: Select all

let m = new Map();
m.set([x, y], 42);
m.has([x, y]); // false

Two different arrays, thus different keys.

There does not seem to be a way for the user to combine keys in a workable way.

Of course it's possible to implement this as a Map of Maps of Maps.... with custom setters and getters, but that just ends up creating way too many Maps, especially for sparse collections.

This could be solved with a single hash table. The javascript engine could just combine the individual hashes. It keeps annoying me that the standard didn't include it, and that the language doesn't give me the tools to solve it properly myself.

Re: Coding: Fleeting Thoughts

Posted: Mon Apr 15, 2019 11:14 pm UTC
by Xanthir
This is something we're planning to solve, just in a more generic way, by adding simple collection types that are compared by value, rather than by reference. That way you could store a Pair or whatever, and then as long as x and y are the same object, all Pair(x,y) objects are ===.

(It's taking a while because the proposal to do so is serving several masters, and balancing the different desires in a worthwhile fashion is complicated. This is adding a fundamentally new type of object to JS, after all!)

Re: Coding: Fleeting Thoughts

Posted: Tue Apr 16, 2019 4:46 pm UTC
by Tub
Thanks for the insight.

I'm having trouble coming up with consumers (besides Set and WeakMap). Surely there's some user code that'd be prettier with these types, but you can always implement your own comparison function. I can't find anything besides Map/Set were you have to rely on behind-the-scenes equality checks. Would you mind elaborating? This seems like a huge addition, so there must be a good reason for it..


It won't solve my immediate near-term problems, but it's good to know that it's being worked on. For now, I'm looking into porting the number crunching to webassembly, where I can bring my own maps. Progress is slow (this is a hobby project, not a work project), but I'll report back eventually.

Re: Coding: Fleeting Thoughts

Posted: Tue Apr 16, 2019 7:26 pm UTC
by Yakk
Value semantics types make entire categories of error less likely. They also permit a whole pile of optimizations, because identity no longer has to be preserved, just value.

Ie, if you copy a value semantics type, the two copies can be elided -- actually have the same identity, and not actually be two different objects -- without telling the programmer, because there is no way to detect the copy in-language.

Static single assignment optimizations open up, for which there is a pile of research and practical applications in other languages.

Now, you can sometimes do this with reference semantics objects, but it takes *work* to prove that you are permitted to do this (and the cost can blow up to do that). With value semantics the proof is free.

It gets even better when you start passing them to functions. When you read a value semantic value and don't modify it? You don't have to read it later to see if it changed. When you modify a value semantic value? Another value semantic value is guaranteed not to change.

Pass two pairs [a,b] [c,d] to a function that uses reference semantics, and modifying one could modify the other (they could refer to the same object!), and entering any unanalyzed code could result in a separate reference to one of them modifying it (which means you have to repeat any reads done after the code, and cannot cache anything).

But that isn't a JS expert talking, just someone who really really really appreciates value semantics in another language, and imagining how it could help JS compilers.

Re: Coding: Fleeting Thoughts

Posted: Tue Apr 16, 2019 8:11 pm UTC
by Xanthir
That's all correct, and are all reasons why I personally want them to exist in JS, so I can use them for CSS Typed OM.

Re: Coding: Fleeting Thoughts

Posted: Tue Apr 16, 2019 9:24 pm UTC
by Tub
Ah, so they don't just have different equality semantics, they're also immutable. That's certainly a lot more powerful.

Re: Coding: Fleeting Thoughts

Posted: Wed Apr 17, 2019 2:18 pm UTC
by Yakk
Tub wrote:Ah, so they don't just have different equality semantics, they're also immutable. That's certainly a lot more powerful.

They don't have to be immutable for any of those benefits.

Lack of identity and reference semantics means you can treat:

Code: Select all

a = b;


as creating a brand new immutable value called "a after you assign b to it". It need not have any relationship to the a *before* you assigned b to it.

Code: Select all

a = init();
if (cond)
  a = b;
do_something(a);

that gets more complex with mutability, but we can still transform it to:

Code: Select all

if (cond)
  do_something(init())
else
  do_something(b);

assuming you can show init() is pure.

Identity is hard to deal with. I swear half of the genius of git is that it discards identity for files.

Re: Coding: Fleeting Thoughts

Posted: Sun Apr 21, 2019 7:31 pm UTC
by Tub
Before going WebAssembly, I wanted to try boosting performance with WebWorkers.

tl;dr:
- doing the task in the main thread: 2-3 ms
- doing the task in a worker: 20-100ms

welp.

This is a webgl game. The task is to prepare an object for rendering, and I have >1000 of these objects. They are prioritized by visibility and distance, but those priorities can change every frame. I cannot just post every task to the workers, because it's not possible to revoke messages or to re-order messages worker-side. Thus I need to queue them in the main thread, then dispatch one at a time whenever a worker is free.

The internet told me there's a >1ms latency for messages. To hide those latencies I expected to either use more workers or to implement a queue-depth of 2-3 for each worker so they never idle. But 100ms? I have no idea how to make that work.

Re: Coding: Fleeting Thoughts

Posted: Sun Apr 21, 2019 8:12 pm UTC
by hotaru
Tub wrote:Thus I need to queue them in the main thread, then dispatch one at a time whenever a worker is free.

maybe try sending them to the workers in batches?

Re: Coding: Fleeting Thoughts

Posted: Mon Apr 22, 2019 10:30 am UTC
by Tub
Batching improves throughput, but also increases per-job latency.

If the latency is greater than one frame, then I need to take care not to submit a job twice. As jobs are defined by (object-id, object-generation), I need - wait for it! - another multi-key Map (or Set).

For now, I've ignored that problem and just did some benchmarks on total work done per time (even if some of that work is discarded later). Trying multiple combinations of worker counts, batch sizes etc. I was too lazy for rigorous numbers or graphs, but the best I could get was 1-2 jobs per frame using workers, on an 8-core CPU. The single-threaded implementation easily does 3-5 jobs per frame.

Those objects aren't exactly small (~4k each), and neither are the replies (up to 50k each, but often empty), so communication overhead is to be expected. But copying a few K shouldn't be that expensive. The effective bandwidth of that IPC connection is lower than the bandwidth of my internet connection.

Re: Coding: Fleeting Thoughts

Posted: Tue Apr 30, 2019 9:38 pm UTC
by Flumble
Blargh, I'm having a very hard time solving the following puzzle (under the assumption there is a solution):

Code: Select all

arr = [????????????????????]
arr[0]  = (arr[8]  + 5) + (arr[1]  - 4)
arr[17] = (arr[1]  - 8) + (arr[13] + 2)
arr[16] = (arr[12] + 1) + (arr[7]  - 3)
arr[5]  = (arr[4]  - 7) + (arr[0]  + 6)
arr[12] = (arr[17] + 2) + (arr[10] - 4)
arr[10] = (arr[9]  - 2) + (arr[3]  + 2)
arr[3]  = (arr[3]  + 5) + (arr[17] - 1)
arr[6]  = (arr[11] - 1) + (arr[16] + 8)
arr[8]  = (arr[16] + 6) + (arr[6]  - 3)
arr[13] = (arr[18] - 3) + (arr[2]  + 7)
arr[4]  = (arr[2]  + 4) + (arr[9]  - 5)
arr[2]  = (arr[13] - 2) + (arr[15] + 1)
arr[7]  = (arr[10] + 8) + (arr[5]  - 9)
arr[11] = (arr[6]  - 6) + (arr[14] + 5)
arr[14] = (arr[17] + 1) + (arr[11] - 3)
arr[1]  = (arr[5]  - 5) + (arr[8]  + 2)
arr[15] = (arr[14] + 2) + (arr[18] - 7)
arr[9]  = (arr[7]  + 1) + (arr[12] - 2)

assert arr == [99,152,183,208,179,221,26,137,190,76,173,74,196,68,219,214,161,147]

First thing I've tried was pulling it through a linear integer solver, which of course didn't work because it's a byte array so all operations are mod 256.
So then I just encoded the code above into SMT statements:

Code: Select all

//declare all symbols as bytes
(declare-const s_0_0 (_ BitVec 8))
...
//encode all assignments as SSA
(assert (= s_0_1 (bvadd (bvadd s_8_0 #x05) (bvadd s_1_0 #xfc)) ))
...
//set the final values equal to the target values
(assert (= s_0_1 #x63))
...

and let Z3 do the magic. (and magic it is, because it's done immediately instead of bruteforcing 256^17 values)
It reports 'sat' and gives values for most symbols, but not all. Does that mean it still has free variables? If so, can I tell it to spew out some candidate values or a system of equations?
[edit]Silly me, of course there are free variables. There's no way s_0_0 can be used for anything because it's overwritten by s_0_1 in the first assignment. And likewise a couple of other elements in the array.

[edit 2]Now I do have a question that I won't figure out a minute later: old_arr[4] seems to be forced at 0x7b (123) but I don't understand why, since all the other elements seem happy to change at a whim. (That is, (assert (not (= s_4_0 #x7b))) is unsatisfiable.) It affects arr[5], arr[7], arr[1] and arr[9] but the set of dependent elements is wildly different between any two of them.

Re: Coding: Fleeting Thoughts

Posted: Wed May 01, 2019 2:49 am UTC
by phlip
Flumble wrote:[edit 2]Now I do have a question that I won't figure out a minute later: old_arr[4] seems to be forced at 0x7b (123) but I don't understand why

To give a hint, the initial value of arr[4] is only read in one place, in the fourth operation of your block:

Code: Select all

arr[5]  = (arr[4]  - 7) + (arr[0]  + 6)
If you can figure out what arr[0] and arr[5] are after this line, then you should be able to figure out what arr[4] was at the time.

Re: Coding: Fleeting Thoughts

Posted: Wed May 01, 2019 11:40 am UTC
by Flumble
phlip wrote:
Flumble wrote:[edit 2]Now I do have a question that I won't figure out a minute later: old_arr[4] seems to be forced at 0x7b (123) but I don't understand why

To give a hint, the initial value of arr[4] is only read in one place, in the fourth operation of your block:

Code: Select all

arr[5]  = (arr[4]  - 7) + (arr[0]  + 6)
If you can figure out what arr[0] and arr[5] are after this line, then you should be able to figure out what arr[4] was at the time.

Thanks. I, too, realized after waking up (more than a minute! :oops: ) that I should've substituted target values (by hand) in the first place get a good view of constants and interdependencies.

Code: Select all

arr[ 2] =  64
arr[ 3] =  57
arr[ 4] = 123
arr[ 9] = 116
arr[10] =  51
arr[11] = 114
arr[14] =  49
arr[15] = 116

arr[7]+arr[12] = 163

arr[1]+arr[8]         =  98
arr[1]       +arr[13] = 153

arr[ 0] = ???
arr[ 5] = ???
arr[ 6] = ???
arr[16] = ???
arr[17] = ???

Well, that settles it, 7 unknowns for 18 numbers won't get me a meaningful answer, just a big space of valid answers.

Re: Coding: Fleeting Thoughts

Posted: Fri May 03, 2019 2:00 pm UTC
by Tub
Instead of writing wasm in a language I know (c++), I decided to learn rust first. It seems interesting, and rust-wasm is hip these days.

Rust has come a long way since the last time I looked at it, and I'm impressed by its current design. Rust 2018 looks worth using.

Except for the borrow checker. I understand the attempt to detect and prevent unsafe constructs, but I'm less than 1000 lines into this project and I've already stumbled upon a situation I'm unable to solve without either creating expensive copies or going unsafe[1]. Even the standard library has to go unsafe almost anywhere they want to produce a mutable iterator.

Why can't they just figure out a way to statically guarantee undecidable properties without restricting expressivity? :roll:

[1]
Spoiler:
I've talked about the actual problem a few posts earlier: I have a collection containing 3d objects, and I need to iterate over them and sometimes (re-)generate their meshes. The complication arises because mesh-generation sometimes needs (read-only) information about other objects, which requires an immutable reference to the collection during iteration. Note that the collection is not a simple vector, so I cannot avoid the iterator by manually indexing.

Preliminary numbers say that mesh-generation is faster than it was using javascript, but I haven't reached feature parity yet.


/edit: this testcase is even simpler:

Code: Select all

fn main() {
  let mut v = [1, 2, 3];
  let a = v.get_mut(1).unwrap();
  let b = v.get(2).unwrap();
  println!("{} {}", a, b);
}

For a suitably insane implementation of a slice, these two references might point to the same element, so the compiler will refuse the code. Just in case.
The whole approach of mutating one element of a collection using information of another, without copying either, is not going to work. Which kinda sucks, because that's what I need to do.