fhtr

art with code

2017-10-09

Ethereum algorithmically

Ethereum is a cryptocurrency with a mining process designed to stress random access memory bandwidth. The basic idea in mining Ethereum is to find a a 64-bit number that hashes with a given seed to a 64-bit number that's smaller than the target number.

Think of it like cryptographic lottery. You pick a number, hash it, and compare the hash to the target. If you got a hash that's below the target, you win 5 ETH.

What makes this difficult is the hashing function. Ethereum uses a hashing function that first expands the 32-byte seed into a 16 MB intermediate data structure using a memory-hard hashing function (if you have less than X bytes of RAM, the hash takes exponentially longer to compute), then expands the 16 MB intermediate data structure into a multi-gigabyte main data structure. Hashing a number generates a pseudo-random walk through the main data structure, where you do 64 rounds of "read 128 bytes from location X and update the hash and location X based on the read bytes."

While the computation part of the Ethereum hashing function isn't super cheap, it pales in comparison to the time spent doing random memory accesses. Here's the most expensive line in the Ethereum compute kernel: addToMix = mainDataStructure[X]. If you turn X into a constant, the hash function goes ten times faster.

Indeed, you can get a pretty accurate estimate for the mining speed of a device by taking its memory bandwidth and dividing it by 64 x 128 bytes = 8192 B.

Zo. What is one to do.

Maximize memory bandwidth. Equip every 4 kB block of RAM with a small ALU that can receive an execution state, do a bit of integer math, and pass the execution state to another compute unit. In 4 GB of RAM, you'd have a million little compute units. If it takes 100 ns to send 128 bytes + execution state from one compute unit to another, you'd get 1.28 PB/s aggregate memory bandwidth. Yep, that's over a million gigabytes per second.

With a million GB/s, you could mine ETH at 150 GH/s. At the moment, 25 MH/s of compute power nets you about $1 a day. 150 GH/s would be $6000 per day. If you can fab ten thousand of them, you'd make sixty million a day. Woooooinflation.


2017-10-08

Fast marching cubes in JavaScript

Marching cubes! Where do they march? What is their tune? The name of their leader, a mystery if any.

Marching cubes works like this:

  1. You have a 3D array of bits and want to create a mesh out of it.
  2. Read a 2x2x2 cube from the array.
  3. Generate a mesh based on the values of the cube.
  4. Repeat for every 2x2x2 cube in the array and concatenate the meshes.

The individual cube meshes work like Lego blocks, they click together to form a seamless mesh.

How to do it kinda fast:

  1. Create cached meshes and normals for each different 2x2x2 bit cube (there are 2^8 of them). You get an array like cubeMeshes[eightBitCubeIndex].
  2. Create a binary array based on the original data. Unroll loops to process in chunks of 8, do it SIMD-like, pass over the original data and spit out ones and zeroes into a Uint8Array. (You could put 8 bits per byte, but it's a hassle.) 
  3. Create a cube index Uint8Array that's going to be filled with the eight-bit cube indexes of each 2x2x2 cube in the data.
  4. Fill the cube index array by marching a 2x2x2 cube over the binary array and converting the read cube values into eight-bit cube indexes. Increment total mesh vertex count by cubeMeshLengths[eightBitCubeIndex].
  5. Allocate Float32Arrays for vertices and normals based on the total mesh vertex count.
  6. Iterate over the cube index array. Write the mesh corresponding to the cube index to the vertex array, offset each vertex with the xyz-coordinates of the cube index. Write the normals corresponding to the cube index to the vertex array.

Source: fastIsosurface.js - demo

This runs in ~150ms on an Intel i7 7700HQ for a 7 million element data array (256x256x109).

Future directions

As you may notice from the source, it's SIMD-friendly, in case you can use SIMD. The algorithm parallelizes easily too.

Web Workers with transferable objects? Transform feedback in WebGL 2 + a reducer kernel to remove empty triangles? Do it in a fragment shader to a float render target? Magic?

Handwaving

The test dataset contains 7 million 16-bit uints which takes about 14 megabytes of RAM. This means that it won't fit in the 7700HQ's 4x1.5MB L3 cache, much less the 4x256kB L2 or the 4x32kB L1.

By compressing the dataset into a bit array, it would fit in 7 megabits, or 875 kB. Processing that with four cores (8 threads) would keep the read operations in the L2 cache. Chunking the processing into 30 kB cubes would keep the reads mostly in the L1 cache.

The output array for the marching cubes step consists of a byte per cube. The original input array has two bytes per element. The bit array has one byte or one bit per element. The output vertex arrays have up to 90 floats, or 360 bytes per cube (but they're very sparse, the average is 1-2 bytes per cube). There's roughly one cube per input array element.

Taking the sum of the above, we get about 1 + 2 + 1 + 1 = 5 bytes per cube. We could process 6000 cubes in a 32kB L1 cache. That might come to 64x10x10 input elements that output 63x9x9 cubes for total memory use of 29406 bytes and 5103 cubes.

How fast would that be? Let's see. You need to read in the input data. That's going to come from RAM at 40 GB/s => something like 0.05 ns per cube. You can crunch it into the binary array as you go: two comparisons, a logical AND, and a store to L1 would work out to 2 ns per input element at 3GHz. For per-cube time, divide by 8 as each element is used by 8 cubes: 0.25ns per cube.

Then read through it with a 2x2x2 window for the cube generation, do a couple multiply-adds. Updating the window requires avg 4 reads per step plus processing to generate the cube indexes, say 4x7 cycles in total.

Then write the vertices to the vertex array. This might take 6 cycles for the array fetch and write.

Add some fudge, 3 GHz clock rate. Each cube takes 4x7 + 6 = 34 cycles. Estimated runtime 12ns per cube (+ 0.25ns for input data processing). Need 10 million cubes for the mesh: 120 ms. Do it in parallel in four L1 caches => 30 ms.

But, uh, it already runs in 150 ms for some meshes. And crunching the input data takes 20 ms of that. In JavaScript. What.

2017-09-23

WebGL 2.0

Started doing some vanilla WebGL 2.0 development this month. I like it. I haven't really ventured further into the new API features than doing 3D textures and GLES 3.00 shaders (which are very nice).

The new parts of the API feel a bit like this: you've got buffers and a shader program. What you do is plug the buffers into the inputs and outputs of the shader and run it. Uniforms? You can use a buffer for that. Textures? You can texImage from a buffer. After you've run your program over your vertex buffers, you can readPixels into a buffer. And there are functions for copying buffer data between buffers (and texture data from one texture to another). You can even write the vertex shader output to a buffer with transform feedback.

The fun tricks this opens up are myriad. Use a vertex shader to create a texture? Sure. Update your shader uniforms with a fragment shader? Uh ok. Generate a mesh in a fragment shader and drop it into a vertex array? Yeaaah maybe. All of this without having to read the data back into JavaScript. I wonder how far you could take that. Run an app in shaders with some interrupt mechanism to tell JavaScript to fetch the results and do something in the browserland.

There is still a dichotomy between buffers and textures, so there are some hoops to jump through if you're so inclined.

2017-09-14

Users for sale

Think of this business model for a bit. A company pays you to use their product. To subsidise manufacturing the product, the company sells you to the highest bidder.

This will completely screw up the market for the product.

If you want to compete in the market, you can't compete on price. You have to offer a higher-quality product for free or even pay more than the competition to the users to attract them to your product. At the same time, you can't make as much money as the incumbent because you don't have as many slaves to sell, and you can't get as much money per slave because you need to compete on price (and likely the quality of your slaves and your knowledge of their best use is lacking due to you being new to this).

But, I hear you say, surely this isn't slavery. And yes, it's a very chilled out form of slavery. The company pays you with digital tobacco. All you have to do is gaze into your phone and endlessly scroll through content. It's not a very demanding job. But you have to do it several hours a day to earn money for the company. Very minimal money, mind. You're getting paid nothing, of course. Otherwise it wouldn't be slavery. The company makes a fraction of a cent per hour of your scrolling work. It's a very low productivity job.

Unless you're one of the superslaves, that is. Superslaves create the content for the endless scroll. They work very hard to bring more slaves to the product, in exchange for control over the slaves they attract, which they can then sell to the highest bidder. Superslaves are still slaves. The company doesn't pay them. (But if your business is selling ad space in popular spaces, you pay the space owner space rent to show ads in space. In which case the superslaves are space landlords instead. The space land might be owned by the company though, provided to the space landlords as a freebie to entice them to create a popular space where they can sell ad space back to the company in which case the space landlords are superspaceslaves instead. Internet business models: rocket science.)

The fun part is this: the users are paid for their endless scrollwork in digital tobacco. The digital tobacco has monetary value. The users should technically declare it in their taxable income. The employer who provides the endless scrollwork to the users should list the users as their employees.

Note that this is only a problem if the employer pays the users in free services. If the company only purchases ad space and resells it to advertisers, the users are not paid by the company and there's no problem. If the users have to pay for the service provided by the company and another company can offer the service for less (but no company can offer it for free), and the users are not sold to the highest bidder, there's no problem.

If the company provides the users a free service funded by ad space on the free service, the users are employees of the company, working for the company to look at ads in the hopes that the ads persuade the users to change their behavior in a way that the advertisers pay for.

2017-09-13

iPhone X launch

The iPhone 8 & X launch feels a bit badly timed (like the iMac Pro, Mac Pro 2 announcements / rumors.) It might be fine though.

What me worry? The iPhone X is the future of the iPhone. It changes the screen form factor a bit, removes the home button, requires minor app redesigns due to the hump and the lack of home button, replaces Touch ID with Face ID and is full on AR twin cameras thing. It's very expensive. And you can't buy it.

The iPhone 8 then. Why would you buy an iPhone 8? Or an SE, or a 6 or a 7. The writing is on the wall. Those iPhones are finished. They don't have Face ID and they have the home button that's about to be deprecated. They look dated and they're cheap.

You can't buy the Apple flagship iPhone at the moment. You can buy the already obsolete iPhone 8, or wait for the X. And the X is suffering from supply problems on its OLED displays that are trickling in from Samsung, who gets the first dibs on the screens for its Galaxy lineup. 

Imagine the scenario. The iPhone X is nowhere to be seen. The few phones that arrive are sold out instantly. You go to the Apple store to play with the X but you can't buy one. You look at the 8 and it looks bad in comparison. So you walk out. And perhaps end up buying something that looks like the X - say a Samsung Galaxy S8. Sure, it's not an iPhone but at least it's not obsolete like the iPhone 8.

I like the X, but I don't like it $999 much. At the same time, I don't want to buy the 8 or lesser iPhones because the X is the future. At $799 the iPhone 8+ looks like especially bad value. It doesn't have the features of the X (even though the specs are similar), doesn't look like the X, it's expensive and it's obsolete.

Launching just the X or just the 8 would've been fine. But launching them both with a delay on the X feels like a bad move. Delay on the 8 would've been fine as it wouldn't eat into the sales of the X. But announcing X depresses sales of 8. A delay on X gives you no replacement sales. Equal specs between 8+ and X make the X seem like a cosmetic thing -> you start thinking "who cares about the phone, just buy the looks" -> buy something that looks like the X.

Na well, I'm probably wrong. 

2017-09-07

Negotiating a Brexit

The Brits are negotiating with the haggling approach, the EU with the "let's do modifications to a reasonable compromise" approach. That's why the Brits seem to be out of their minds like the wino at the liquor store trying to haggle down the price of a 20 quid bottle of whiskey by starting with a 5 pound offer. And to the Brits, the EU seems to be very inflexible like the shopkeeper who says that prices are fixed (but there's a bit of leeway depending on what else you buy and how you behave).

This is pretty hard to fix after the fact. If the Brits go with "okay, let's do it your way", it'll look like they're suddenly giving a lot of ground. If the EU starts doing a haggling approach with an unreasonable first offer, it'll look like they've gone bonkers and are negotiating in the wrong direction.

For the Brits, the best approach is to keep haggling to extract concessions. They're already unreasonable so there's very little to lose by slowly moving towards the reasonable compromise. You can even do yanks in the other direction to see if you can nudge loose any extras.

For the EU, the best approach is to stop negotiating until the Brits are at the reasonable compromise. Then you can start figuring out the modifications and get the deal done. There's no point in negotiating while the Brits are approaching the middle ground, so it's best to just end negotiation rounds once you find out that they're not there yet.

The problem with these approaches is that while they're good optics at home, they antagonize the British audience towards the EU and the EU audience towards the Brits. The Brits seem like welfare queens, wanting to have everything without doing anything, whereas the EU looks like a bunch of rigid bureaucrats, unable to do a deal.

To counter this, the two sides appeal to the public on the other side. The EU ends up courting the British public by promises that they'll retain their citizenship and that the negotiations are mostly about boring bureaucratic stuff with the out-of-touch British government. The Brits end up telling that other Europeans should bugger off from the blighted isles before the pox descends upon them.. um, wait what? There's no British PR outreach, just Home Office hardliners ranting about their clients. Perhaps this should change?

To bridge the gap between the negotiation strategies, the EU could gradually shift more towards a haggling approach by moving the goalposts. Apply time pressure, give concessions on minor things, but start going for a worse deal for the Brits on things that matter. Then you can start doing haggling, give concessions and move towards a reasonable compromise once again. The other way to get to the unreasonable offer necessary to start haggling is to have some big shift - say you change the negotiator or that some unnamed governments have insisted to change the position in a big way because October is approaching or that the skies are cloudy therefore we need to insist on triple payments, all the stolen EU tax money in the tax havens, and the reunification of Gibraltar and Ireland.

The Brits could bridge the gap by misstating the EU position as something unreasonable that they've never said, then haggle against this strawman position until the EU position as stated by the Brits agrees with the actual EU position, and the Brit position is also at the reasonable compromise. The other way would be a big shift of their own, something like "Oh! Right! We misread your proposal. Yes, this seems much more agreeable, let's work from here then."

Thing with haggling: both sides get big wins in the process when going from unreasonable to reasonable. That's the psychology. If you don't get big wins, you'll get frustrated. The "modifying a reasonable compromise" process on the other hand nets you a few small wins, a few small losses. It's not as exciting and can be done a lot faster.

2017-08-31

Post-Brexit Britain

How will Britain look like after the Brexit process has been completed and Britain is no longer a member of the European Union? The first step of the post-war government is to negotiate a trade deal with the EU to trade with the other European countries with minimal hassle. This trade deal will be an easy one, as EU standards already follow the British standards.

All that is needed is an agreement on the future evolution of those standards and a place to settle disputes, and the budget for running that place. Most likely, the standards will be driven by the EU, with the UK getting a minor voice in building them, UK could potentially get an equal vote with the other member states.

As for the place to settle trade disputes: as WTO is not really up to dealing with issues with British sensibilities, it's likely that the place would be closer to London. Perhaps in Luxembourg, a relatively neutral country between Brussels and London.

Making standards isn't cheap, there needs to be some budget for all the work required for that. This budget would be split between the EU and the UK in a proportional fashion. There will need to be some further integration of the UK and EU markets so that free trade Britain can flex its wings and fly on unhindered trade flows.

Domestically, there will be need for some extra revenue for the state to pay for the incurred one-time costs from the Brexit process. The UK is sitting on a sizable treasure chest in the form of untaxed corporate revenue squirreled away in its off-shore tax havens. A reasonable course of action would be to impose a one-time 30% levy on all money held in UK tax havens, followed by a modest increase in the income and corporate taxes in the tax havens, perhaps to 20% or so.

In order to maintain public order and defend against foreign propaganda, the UK government would require that media organizations operating in the UK need to have 60% British ownership and the controlling owners need to be British nationals who are resident in the UK 183 days per year or more. Any broadcast or internet media organisations falling afoul of the ownership laws would be banned from operating in the UK to prevent UK's independence being eroded by targeted hostile falsehoods. UK can use their trade deal with China to acquire the technology needed to run an firewall around the islands. You could call it Hadrian's Firewall.

The firewall would open the British marketplace to British service providers, British internet utilities and British media companies. No longer would Britain have to pay billions of dollars of tribute to overseas companies for providing simple utilities like internet search, messaging boards and advertising services. Silicon Roundabout would grow into Silicon Britain, with British companies exporting world-class high-value-add services to billions of people around the world.

To meet the needs of an aging population, the NHS needs to be beefed up as the retirees can no longer be shuffled off to Spain. To pay for the NHS boost, there will have to be some mild tax increases on capital gains, foreign entities, corporations and high income earners. The government would be well advised to set the highest income tax bracket at 55%, with corporate revenues after salaries also subjected to progressive taxation ranging from 15% to 55% for the largest multinationals.
Given the increased tax income, Britain could well afford to build new cities and developments to sell affordable housing to all segments of the population, multiplying the size of the British property market. With millions of newly-minted homeowners, the proportion of income spent on non-productive rental redistributions would fall and release a tsunami of private investment and increased productivity as motivated entrepreneurial homeowners take their stand and build billions of pounds worth of companies and create millions of new jobs.

To further prevent Brexit from causing great harm to the people of Britain, the British government needs to support its citizens. The one best way to improve the lot of the ordinary Briton is to reduce taxes on necessities. By getting rid of the VAT, the people of Britain will have 20% more money to spend on rebuilding Britain. For a family living on 20,000 pounds a year, this would free an extra 4,000 pounds to invest into their future and the future of Britain.

Blog Archive

About Me

My photo

Built art installations, web sites, graphics libraries, web browsers, mobile apps, desktop apps, media player themes, many nutty prototypes, much bad code, much bad art.

Have freelanced for Verizon, Google, Mozilla, Warner Bros, Sony Pictures, Yahoo!, Microsoft, Valve Software, TDK Electronics.

Ex-Chrome Developer Relations.