Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

JS1k demo: “Highway at Night”

js1k.com

Post reply on HN
Print view View original

61–70 of 100 posts

Re: JS1k demo: “Highway at Night”

#61

Post by mistercow »

adamcanady wrote: post #4

Wow. I can make sense of a little bit of the original source, but I wonder more how RegPack [0] works to compress it into that final submission! As a side note: I'm in college now and looking to propose an independent study on compression. Any suggested readings or algorithms I should look into? [0] https://github.com/Siorki/RegPack

For lossless compression, start out by reading up on run length encoding, which is about as simple as it gets. Then there's DEFLATE, which is what's behind gzip. You'll also want to read up on Huffman coding and arithmetic coding. One of the newer ideas in lossless compression is "context mixing", which is definitely worth reading up on. The Burrows–Wheeler transform is pretty fascinating, albeit slow, so you might want to read about that as well.

Lossy compression (which RegPack is actually an example of), typically involves lossless compression plus a preprocessing step to discard information so that the lossless compressor can do a better job.

The techniques for discarding information vary based on application. For images and audio, the most successful techniques tend to involve working in frequency space, so you'll want to read up on the FFT and related transforms.

For code compression, you have different constraints when discarding information because you have to produce a program with identical output to the original. Simple techniques involve removing comments and renaming variables to have shorter names. More advanced techniques involve more complex transformations of the AST, including language-specific tricks like wrapping javascript in a "with(Math){}" block.

Hope some of that helps.

Re: JS1k demo: “Highway at Night”

#62

Post by nmjohn »

ape4 wrote: post #58

I saw the double tilde (~~) in the code and wondered what it was. Of course, single tilde is the bitwise not operator. Googling finds that double tilde is a faster Math.floor(). http://stackoverflow.com/questions/5971645/what-is-the-doubl...

Learning about bitwise operators (and everything they entail - so binary in general, endianness, etc) was without a doubt the most beneficial thing I've ever done for my programming abilities.

It was a complete eye opener to how computers work on a far more fundamental level than any other aspect of programming had previously revealed to me.

For anyone without a traditional CS educational background, if you don't know much about bitwise operations or binary, I highly recommend sitting down and spending a few hours exploring them - it will make you think about certain aspects of programming in a very different manner, which - at least for me - resulted in writing much better code.

Aside: While the double tilde is handy, I use the single tilde operator far more often in javascript. If you precede an indexOf statement with a tilde, it essentially turns `indexOf` into `contains`.

    if(~someStringOrArray.indexOf(searchTerm))
It works because indexOf returns the index the term is found at, or -1 if it isn't found. This means 0 is actually a successful result, but Boolean(0) = false. But bitwise NOT will clear all of that up:

    ~(-1) = 0 (evaluates as false)
    ~(0) = -1 (evaluates as true)
Edit: I'm not suggesting everyone go off and use ~indexOf all the time - I was simply sharing a related javascript bitwise "trick".

Re: JS1k demo: “Highway at Night”

#63

Post by mistercow »

vardump wrote: post #60
sampo wrote: post #32

Earlier quoted context omitted.

Well that is a lossy compression, can work nicely to some data (e.g. images), but totally irrelevant in the context of source code compression.

Lossy compression might be just fine for source code, as long as the lossy part is still functionally equivalent. Think 1000.0 vs 1E3, printf("foo") vs puts("foo"), etc.

And in fact, RegPack is lossy compression (as are all minifiers). The transformation is totally irreversible.

Re: JS1k demo: “Highway at Night”

#64

Post by zoul »

nmjohn wrote: post #62
ape4 wrote: post #58

I saw the double tilde (~~) in the code and wondered what it was. Of course, single tilde is the bitwise not operator. Googling finds that double tilde is a faster Math.floor(). http://stackoverflow.com/questions/5971645/what-is-the-doubl...

Learning about bitwise operators (and everything they entail - so binary in general, endianness, etc) was without a doubt the most beneficial thing I've ever done for my programming abilities. It was a complete eye opener to how computers work on a far more fundamental level than any other aspect of programming had previously revealed to me. For anyone without a traditional CS educational background, if you don't kno…

I would probably hate you for not writing plain “!=-1” instead.

Re: JS1k demo: “Highway at Night”

#65

Post by tlrobinson »

nmjohn wrote: post #62
ape4 wrote: post #58

I saw the double tilde (~~) in the code and wondered what it was. Of course, single tilde is the bitwise not operator. Googling finds that double tilde is a faster Math.floor(). http://stackoverflow.com/questions/5971645/what-is-the-doubl...

Learning about bitwise operators (and everything they entail - so binary in general, endianness, etc) was without a doubt the most beneficial thing I've ever done for my programming abilities. It was a complete eye opener to how computers work on a far more fundamental level than any other aspect of programming had previously revealed to me. For anyone without a traditional CS educational background, if you don't kno…

You definitely should learn bitwise operators, but if other people have to work with your code I'm not generally in favor of applying them in clever ways where there's a slightly more verbose but much more readable solution (e.x. "~x.indexOf(y)" vs "x.indexOf(y) !== 0"... just type the extra 3 characters)

Re: JS1k demo: “Highway at Night”

#66

Post by tlrobinson »

userbinator wrote: post #55

Reminds me of this 4k JS demo which has a somewhat similar concept but is big enough to contain sound : http://www.pouet.net/prod.php?which=61668 Making of: http://www.ylilammi.com/webgl/highway4k/Making%20of%20Highwa...

Impressive, that totally hung my machine for a couple minutes (Chrome/OS X)

I'd recommend watching the video instead.

Re: JS1k demo: “Highway at Night”

#67

Post by Cthulhu_ »

nmjohn wrote: post #62
ape4 wrote: post #58

I saw the double tilde (~~) in the code and wondered what it was. Of course, single tilde is the bitwise not operator. Googling finds that double tilde is a faster Math.floor(). http://stackoverflow.com/questions/5971645/what-is-the-doubl...

Learning about bitwise operators (and everything they entail - so binary in general, endianness, etc) was without a doubt the most beneficial thing I've ever done for my programming abilities. It was a complete eye opener to how computers work on a far more fundamental level than any other aspect of programming had previously revealed to me. For anyone without a traditional CS educational background, if you don't kno…

Or someString.contains(searchTerm) - https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...

Re: JS1k demo: “Highway at Night”

#68

Post by grecy »

nmjohn wrote: post #62
ape4 wrote: post #58

I saw the double tilde (~~) in the code and wondered what it was. Of course, single tilde is the bitwise not operator. Googling finds that double tilde is a faster Math.floor(). http://stackoverflow.com/questions/5971645/what-is-the-doubl...

Learning about bitwise operators (and everything they entail - so binary in general, endianness, etc) was without a doubt the most beneficial thing I've ever done for my programming abilities. It was a complete eye opener to how computers work on a far more fundamental level than any other aspect of programming had previously revealed to me. For anyone without a traditional CS educational background, if you don't kno…

> if(~someStringOrArray.indexOf(searchTerm))

Do you think the person maintaining your code 2-5 years from now will understand that easily and quickly?

For maintenance, it's important to be as clear as possible, not as tricky as possible.

Re: JS1k demo: “Highway at Night”

#69

Post by Wintamute »

rimantas wrote: post #53
Wintamute wrote: post #29

Earlier quoted context omitted.

I'm glad some people care about browser performance, care about creating art and apps that push performance, because without them we won't get to that future where there's a viable, open, free, standards based platform that people can use to challenge the dominance of truly closed source native app platforms. So yes I am shocked to hear that you don't care. And I'm a bit shocked to see you rant at a person that simpl…

You know, nobody stops anyone form making open source native apps.

I said native app platforms not native apps.

Re: JS1k demo: “Highway at Night”

#70

Post by nmjohn »

Cthulhu_ wrote: post #67
nmjohn wrote: post #62

Earlier quoted context omitted.

Learning about bitwise operators (and everything they entail - so binary in general, endianness, etc) was without a doubt the most beneficial thing I've ever done for my programming abilities. It was a complete eye opener to how computers work on a far more fundamental level than any other aspect of programming had previously revealed to me. For anyone without a traditional CS educational background, if you don't kno…

Or someString.contains(searchTerm) - https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...

> This is an experimental technology, part of the Harmony (ECMAScript 6) proposal.

It only works in firefox and if I remember correctly, it is no longer part of the latest ECMA 6 spec.

Post reply on HN