Coding: Fleeting Thoughts

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Coding: Fleeting Thoughts

Postby Yakk » Sun Feb 10, 2019 4:08 pm UTC

Why would commits take 5 minutes?!
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

commodorejohn
Posts: 1182
Joined: Thu Dec 10, 2009 6:21 pm UTC
Location: Placerville, CA
Contact:

Re: Coding: Fleeting Thoughts

Postby commodorejohn » Sun Feb 10, 2019 4:26 pm UTC

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.
"'Legacy code' often differs from its suggested alternative by actually working and scaling."
- Bjarne Stroustrup
www.commodorejohn.com - in case you were wondering, which you probably weren't.

User avatar
Xenomortis
Not actually a special flower.
Posts: 1448
Joined: Thu Oct 11, 2012 8:47 am UTC

Re: Coding: Fleeting Thoughts

Postby Xenomortis » Sun Feb 10, 2019 6:58 pm UTC

I suspect something other than ~500 line text files are being committed...
Image

User avatar
Flumble
Yes Man
Posts: 2249
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Coding: Fleeting Thoughts

Postby Flumble » Sun Feb 10, 2019 7:48 pm UTC

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.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Coding: Fleeting Thoughts

Postby Yakk » Mon Feb 11, 2019 9:13 pm UTC

"oh, git can handle binary blobs well enough"


Hahahahahahahahahaahahahahahahahaha

ahum.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
Flumble
Yes Man
Posts: 2249
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Coding: Fleeting Thoughts

Postby Flumble » Mon Feb 25, 2019 5:12 pm UTC

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?

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Coding: Fleeting Thoughts

Postby Xanthir » Mon Feb 25, 2019 7:28 pm UTC

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.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 4060
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

Re: Coding: Fleeting Thoughts

Postby Soupspoon » Mon Feb 25, 2019 8:46 pm UTC

I agree;

User avatar
Flumble
Yes Man
Posts: 2249
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Coding: Fleeting Thoughts

Postby Flumble » Tue Feb 26, 2019 12:00 am UTC

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)

Tub
Posts: 472
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Coding: Fleeting Thoughts

Postby Tub » Tue Feb 26, 2019 1:01 pm UTC

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?

User avatar
Flumble
Yes Man
Posts: 2249
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Coding: Fleeting Thoughts

Postby Flumble » Tue Feb 26, 2019 2:50 pm UTC

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?)

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Coding: Fleeting Thoughts

Postby Xanthir » Tue Feb 26, 2019 3:03 pm UTC

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.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Flumble
Yes Man
Posts: 2249
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Coding: Fleeting Thoughts

Postby Flumble » Tue Feb 26, 2019 3:35 pm UTC

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.
Last edited by Flumble on Thu Feb 28, 2019 4:23 pm UTC, edited 2 times in total.

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Coding: Fleeting Thoughts

Postby Xanthir » Tue Feb 26, 2019 5:43 pm UTC

Ah! I didn't realize that plain-for would establish the correct binding scopes for block-scoped variables! That's exciting!
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Tub
Posts: 472
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Coding: Fleeting Thoughts

Postby Tub » Tue Feb 26, 2019 10:50 pm UTC

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!)

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Coding: Fleeting Thoughts

Postby Xanthir » Wed Feb 27, 2019 1:03 am UTC

...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.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
phlip
Restorer of Worlds
Posts: 7572
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Coding: Fleeting Thoughts

Postby phlip » Wed Feb 27, 2019 1:20 am UTC

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...

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Coding: Fleeting Thoughts

Postby Xanthir » Wed Feb 27, 2019 1:49 am UTC

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.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Tub
Posts: 472
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Coding: Fleeting Thoughts

Postby Tub » Wed Feb 27, 2019 10:44 am UTC

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.

User avatar
Flumble
Yes Man
Posts: 2249
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Coding: Fleeting Thoughts

Postby Flumble » Wed Feb 27, 2019 12:49 pm UTC

Tub wrote:Hint: that's not an object literal there.

whyyyyyy.jpg
whyyyyyy.jpg (29.16 KiB) Viewed 7975 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:

User avatar
phlip
Restorer of Worlds
Posts: 7572
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Coding: Fleeting Thoughts

Postby phlip » Wed Feb 27, 2019 1:17 pm UTC

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...)

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

DavidSh
Posts: 214
Joined: Thu Feb 25, 2016 6:09 pm UTC

Re: Coding: Fleeting Thoughts

Postby DavidSh » Wed Feb 27, 2019 3:17 pm UTC

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}.

User avatar
Flumble
Yes Man
Posts: 2249
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Coding: Fleeting Thoughts

Postby Flumble » Wed Mar 06, 2019 10:41 pm UTC

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)

Tub
Posts: 472
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Coding: Fleeting Thoughts

Postby Tub » Thu Mar 07, 2019 3:41 am UTC

frames are just windows. Isn't there something like myIframe.contentWindow.history.back() ?

operator[]
Posts: 156
Joined: Mon May 18, 2009 6:11 pm UTC
Location: Stockholm, Sweden

Re: Coding: Fleeting Thoughts

Postby operator[] » Sat Mar 23, 2019 7:24 pm UTC

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.)

gd1
Posts: 352
Joined: Wed Nov 14, 2012 5:42 am UTC

Re: Coding: Fleeting Thoughts

Postby gd1 » Fri Mar 29, 2019 7:02 am UTC

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;
}
There is no emotion more useless in life than hate.

Tub
Posts: 472
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Coding: Fleeting Thoughts

Postby Tub » Thu Apr 11, 2019 2:43 pm UTC

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.

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Coding: Fleeting Thoughts

Postby Xanthir » Mon Apr 15, 2019 11:14 pm UTC

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!)
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Tub
Posts: 472
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Coding: Fleeting Thoughts

Postby Tub » Tue Apr 16, 2019 4:46 pm UTC

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.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Coding: Fleeting Thoughts

Postby Yakk » Tue Apr 16, 2019 7:26 pm UTC

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.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Coding: Fleeting Thoughts

Postby Xanthir » Tue Apr 16, 2019 8:11 pm UTC

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.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Tub
Posts: 472
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Coding: Fleeting Thoughts

Postby Tub » Tue Apr 16, 2019 9:24 pm UTC

Ah, so they don't just have different equality semantics, they're also immutable. That's certainly a lot more powerful.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Coding: Fleeting Thoughts

Postby Yakk » Wed Apr 17, 2019 2:18 pm UTC

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.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Tub
Posts: 472
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Coding: Fleeting Thoughts

Postby Tub » Sun Apr 21, 2019 7:31 pm UTC

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.

User avatar
hotaru
Posts: 1045
Joined: Fri Apr 13, 2007 6:54 pm UTC

Re: Coding: Fleeting Thoughts

Postby hotaru » Sun Apr 21, 2019 8:12 pm UTC

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?

Code: Select all

factorial product enumFromTo 1
isPrime n 
factorial (1) `mod== 1

Tub
Posts: 472
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Coding: Fleeting Thoughts

Postby Tub » Mon Apr 22, 2019 10:30 am UTC

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.

User avatar
Flumble
Yes Man
Posts: 2249
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Coding: Fleeting Thoughts

Postby Flumble » Tue Apr 30, 2019 9:38 pm UTC

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.

User avatar
phlip
Restorer of Worlds
Posts: 7572
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Coding: Fleeting Thoughts

Postby phlip » Wed May 01, 2019 2:49 am UTC

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.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
Flumble
Yes Man
Posts: 2249
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Coding: Fleeting Thoughts

Postby Flumble » Wed May 01, 2019 11:40 am UTC

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.

Tub
Posts: 472
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Coding: Fleeting Thoughts

Postby Tub » Fri May 03, 2019 2:00 pm UTC

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.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 6 guests