HNHacker News
TopNewBestAskShowJobs

CHY872

1,379 karma · joined April 8, 2014

submissionscomments
CHY872··on Ask HN: Why did stack-based CPUs lose out?
I might be wrong but it seems a little suspect to call Ia64 superscalar because of that. When I hear superscalar, I generally expect to see a processor dynamically checking data dependencies at runtime, and perhaps executing multiple instructions depending on those data dependencies. With out of order execution added on top, I'd additionally expect to see a structure like a reorder buffer to allow results to be written to RAM in the same order as the logical execution.

I think that encoding the parallelism into the instructions would generally not be considered as superscalar, it's an entirely different technique. Most texts I've read would explicitly separate out VLIW and EPIC from superscalar processors. There are plenty of ways of getting parallelism - for example one could probably view SIMD or even some CISC instructions as a form of this - as far as I know, VLIW and superscalar processors are just considered different from this perspective.

CHY872··on Ask HN: Why did stack-based CPUs lose out?
Building a solid computer stack (hardware through software) is an exercise in mechanical sympathy, understanding the traits of the underlying components which enable the practitioner to get as much out of it as possible. The software should do the thing that the software is good at, and the hardware should do the things that the hardware is good at, and neither exists in a vacuum, both should be aware of the constraints of the other.

For one example, about 25 years ago Intel made a processor called Itanium which used 'VLIW' (very long instruction word) instructions as opposed to x86. In this case, a lot of the complexity of operating a processor is shifted into the compiler, since individual CPU instructions may perform complex operations. In a modern processor, instructions are 'simple', and the processor is responsible for finding the data dependencies that allow multiple instructions to be executed in parallel (this is called 'superscalar' processing). With Itanium, the compiler author can encode such individual operations into more complex instructions which can be executed in parallel, all at once. So, where in x86 I might have in 3 different instructions (add r1, r2, sub r3, r4, mul r5, r6), with Itanium I might be able to combine all of those into a single instruction at compile time. By doing this, in theory we can remove a lot of the complex superscalar logic from the processor, devote more of the chip to execution units and achieve more overall performance.

One problem here is that the compiler may not actually know what parallelism is possible. For example, the latency of a given instruction may vary from chip to chip. The number of execution units for a single operation may vary. Our code is now very highly optimised for a particular CPU, we may not see natural speedups as newer processors are made, newer processors might not even support the code we've written without a translation layer. Taken to extremes, we lose the universality of software (the ability to change the hardware without rebuilding the software). VLIW chips are viable, but they're typically used in more isolated use cases (like DSPs) where it's reasonable to recompile the software for every chip (and where perhaps there is lots of parallelism in the problem space).

State machines essentially have similar issues. High performance processors tease out the data dependencies between instructions in order to perform superscalar processing, which is key to good performance in a modern processor. Stack machines make it very difficult to understand data dependencies because in principle all data depends on all other data, a post-processing step is required (which is considerably more expensive than the processor equivalent of converting to SSA form). Modern register machines rely heavily on register renaming to ensure that both superscalar processing and pipelining work well with each other - maintaining similar performance with a stack machine would lead to similar solutions, and so very likely switching from a register machine to a stack machine would likely look like having a translation layer on the chip, from the stack machine back into a register-like language.

Stacks do exist in a few places these days. The JVM clearly does it - Java is 'register oriented' for the programmer, the JVM instruction set is stack oriented, and the runtime converts it back into a register oriented machine code. Another example is the ARM Jazelle extensions which allow some ARM processors to directly execute Java bytecode. Here, the bytecode is converted into the machine code as an extra stage in the processor pipeline, adding overhead.

BLAB: - There isn't much advantage to stack machines. It's relatively straightforward to translate between the two. - Modern processors are architecturally closer to register machines, and a lot of the techniques used to make them fast would have to be replicated on a stack machine. - Because any decisions at this level of the stack are effectively invisible to the user in modern tech, it's beneficial to go for the simplest solutions to any given problem, which here is to use a register machine at the hardware level.

CHY872··on Should small Rust structs be passed by-copy or by-borrow? (2019)
I'd expect your claim to be true whenever the callee is inlined into the caller. In this case, the compiler has all the relevant information at the right point in time. As other commenters have pointed out, by enabling inlining the author has gone down a rabbit hole somewhat unrelated to the question, because any copies can be simply elided.

If there's no inlining at play, I'd expect vast differences to be possible. For example, imagine a chain of 3 functions - f calls g, g calls h, where one of the arguments is a 1kB struct and the options are passing by copy or by borrowing. In this case, each stack frame will be 1kB in size in the copy case and there will be a large performance overhead as opposed to the by-reference case. One would expect simply calling the function to be similar in overhead to an uncached memory load.

Within a single crate the inlining is possible, with multiple crates it's only possible with LTO enabled (and I'm not sure how _probable_ it is that the inlining would occur).

In either case, the difference between a 32 byte and 8 byte argument in terms of overhead is likely meaningless - the sort of thing to be optimized if profiling says it's a problem as opposed to ahead of time.

CHY872··on EU adopts global minimum 15% tax on big business
To make sure I understand your point, is the argument that without a revenue tax, you're incentivised to sell as much of your stuff as possible, whereas with a revenue tax you're incentivised to maximise your margin, and this makes things inefficient for everyone downstream of you?
CHY872··on Chris Seaton has died
Oh man, it was always awesome to find something from this dude! He'll be missed.
CHY872··on TSMC ups Arizona investment from $12B to $40B with second semi fab
While semiconductor fabs are highly automated, the machines are complex enough and do extreme enough things that they break a lot, requiring human intervention. MTBF for many of the machines used can be measured in hours, it's not like you can set up and go home. TSMC has around 65k employees overall - a cursory search did not yield their makeup by job breakdown, although from 1997 through 2003 around 50% of their employees were 'factory' workers via [0].

I'd expect high-margin items like semiconductors to be more amenable to onshoring anywhere - certainly Intel has almost all of its fabs in highly developed countries, but I think this is hardly a cost efficiency move - rather it's a hedge against the failure of globalization and the risk of the US losing access to advanced semiconductor technology in case of strife in Taiwan. Russia has already lost this access. TSMC took in about $56B in '21, of which about $28B was 'cost of revenue', the amount they needed to spend on supporting this revenue (marketing, legal, production, e.g., not building factories or R&D). There's certainly room for increased production costs while maintaining a profit.

[0] - https://www.researchgate.net/figure/TSMC-personnel-structure...

CHY872··on Tell HN: Cloudflare Is Blocking Piped
Yes, the gpg piece provides that functionality nicely. However, it’s exceedingly common for the mirrors to not be provided over TLS for cost reasons. Netflix switched to serving video over TLS for no other reason than to promote the usage of TLS (after a lot of custom engineering (pki on cpu, crypto on nic iirc?) to reduce the overheads of doing this.
CHY872··on Westinghouse sees a tech disrupter in its eVinci microreactor
Charging 20 Teslas at maximum rate sure, but that could also be viewed as fully charging 1600 Teslas per day, or steady state providing the energy for about 12k Teslas (assuming 10-15k miles per year per car). Likewise, based on my own electricity bills, 1k houses is closer to 3000-5000.

Obviously, peak load vs average load is very important so I wouldn’t expect the energy to go that far, but connected to a big battery… probably, right?

CHY872··on Tell HN: Cloudflare Is Blocking Piped
I think the ability to put TLS in front of a non-TLS'd website comes of a few properties:

1. It's probably better than nothing. 2. It's a legacy thing.

A company like Cloudflare has to make a choice - how frequently do we break users who've set up their site in a way that is no longer in line with security best practices? It looks like the decision they've made is to break infrequently. Certainly the site I set up in 2014 when their free TLS was new still runs, and I haven't made changes.

I believe that you can set up strict TLS between Cloudflare and the end host if you choose, but it's up to you. I think in that instance, your 'little control you get' is actually more control, no?

And, if you look back even a few years, TLS was both uncommon and expensive. Cloudflare was a pioneer by offering free TLS certificates in I think 2014 (only 8 years ago!). LetsEncrypt started in 2015 and was niche for quite some time. I think even now you can find Linux distros preferring to ship their data over HTTP with GPG-keys recommended for the security. Of course in 2022 even simple sites should be TLS'd, but Cloudflare's existed for a while.

And, TLS to the client but plaintext from CDN to site is still better than cleartext the whole way, because it (generally) stops the ISP from snooping on its customers.

CHY872··on New Hampshire set to pilot voting machines that use software everyone can see
In the UK you usually have 1-3, fewer since we left the EU. However, the number of ballots is relatively immaterial for two reasons:

Spend: In the UK, price of counting ballots is far lower than price of paying poll booth staff. It costs approximately £0.10 per person (note, not per ballot) in the UK to count ballots in a nationwide election (as opposed to about £0.35 on keeping polling booths open). It’s likely that if the number of ballots went up by a factor of 10, further efficiencies would be found, but simple ‘ballots counted per hour’ metrics imply that the marginal cost should be relatively affordable.

Difficulty: While running a fair and free election is undeniably challenging, it naively would appear to be much less work than E.g. the USPS does each day to deliver the daily 300M pieces of mail.

CHY872··on New Hampshire set to pilot voting machines that use software everyone can see
In the UK all ballots are hand counted, and the counting is done within a day.

I would expect that the amount of time it takes to tally a paper election is related to how many people you have counting.

CHY872··on Microservices – Please, Don’t (2016)
There are many excellent problem solving techniques in software engineering. Taken as religion, to extremes, most of these will lead the zealot to destruction. Microservices have their place, as do monoliths.

The author's most valuable point is roughly 'don't believe the hype' - and that's timeless. On the specifics, they're certainly right on each point, but they missed the (imo main) one of 'by forcing a conceptual boundary between different pieces of the application, one can build true silos around competences and so scale their org more effectively'. Put simply, a 200 person monolith will usually feel like it has 200 people working on it. That same org split into 5 groups of 40 can be more nimble. In some cases this is due to infra ('we need to get off Java 8' is easier if the software can be run in 5 pieces). In some cases this is due to problem scope (less intertwining of concepts possible).

CHY872··on Microservices – Please, Don’t (2016)
It's not necessarily much in the way of extra steps. The Elasticsearch Cloud-on-K8s operator IMO does this quite well.

You define 'node sets' which each play a role in the cluster. Node sets can have tags applied to them, and this affects the procedures they run.

For example, you could say:

1. Let's have a node set of 3 master nodes. 2. Let's have a nodeset of 10 hot data nodes, backed with SSDs and tagged with 'hot'. 3. Let's have a nodeset of 5 cold data nodes, backed with HDDs and tagged with 'cold'. 4. 4 client nodes for load balancing.

You could also say - let's have 3 nodes that play all roles.

On startup, each node starts only the parts of the app that correspond to the roles it's playing.

It's fairly seamless and I think this model would expand quite nicely to 'business logic' services

Anecdotally, have seem some people attempt to retrofit a poor man's version of this model into their microservice in response to e.g. performance problems.

CHY872··on Why are D-sharp and E-flat considered to be two different notes?
I don't think GP was particularly making the point that it was innately impossible to tune an organ and a piano the same, just that it's common for them to be tuned differently (especially in European churches). Same with harpsichord and piano (where a harpsichord is not tuned to concert A).

Either way, hope you enjoyed the citations - I found them interesting - the one about Bach writing in specific keys so as to match the instruments he's working against reflects a different kind of craftsmanship and concern than one would see from most composers in the 21st centruy!

CHY872··on Why are D-sharp and E-flat considered to be two different notes?
I don't think that's quite GP's claim. They're not necessarily saying that organs and keyboards of the same heritage had different tuning (though it's well documented that instruments had different tuning according to region even through the 1700s and 1800s), rather that historic organs which retain their original temperament sound very different to modern keyboards. Here's an article supporting this. It refers to different rates of beating in different tuning regimes, comparing equal temperament to 'cornet-ton' type things.

Because it's common for organs to be hundreds of years old, and it's common for people to want historic organs to sound as close to how they did when they were made as possible because it's uncommon for them to play in non-vocal ensemble, this leads to a relatively common situation where an organ played today may well be tuned very differently to a piano played today. Depending on the organ.

https://www.eunomios.org/contrib/francis2/francis2.pdf

Here is a second article on organs by one manufacturer tuned in 'meantone' https://www.bach-cantatas.com/Topics/Meantone.htm. It's also the case that harpsichords were commonly tuned in meantone https://www.harpsichord.org.uk/wp-content/uploads/2015/04/te... which might actually support the claim that historic non-organ keyboards sounded different from organ keyboards (specifically, if Bach didn't like the mean-tone organs he played and it was common to tune harpsichords in meantone, that would seem to provide some evidence for both temperaments existing and sounding different on the different types of instrument in the same historic period).

CHY872··on Creating Shazam in Java (2010)
The purpose of a patent is to encourage global innovation by granting exclusive rights for commercialising technology for a limited time in response to sharing how it works.

Roughly, if you invent PageRank and keep it internal to your search company, you can exploit that idea but if someone else comes up with it they can exploit it too. If you invent PageRank and patent it, the whole world knows how it works but can’t use it for 20 years without paying you.

Generally in case of a violation you’d want to sue for damages, whether that be licensing costs not paid, or missed revenue on your own side.

This probably then ends up in a bit of a grey area. Shazam would be within their rights to exert the patent, but the damages are likely so minimal to be outweighed by the cost of litigating the case, which means that the C&D is a little too chilling for my liking. Basically, any penalty would be lawyers fees - author hasn’t tried to commercialise it, it doesn’t reduce Shazam’s revenue at all. Are there any damages at all?

And then, few would argue (I think) that simply implementing a patent for educational purposes constitutes infringement. My uni course contained an implementation of PageRank. Is publishing the course notes then infringement? Arguable it’s anti-goal to discourage actually spending time learning about the innovation beyond just reading the patent doc - otherwise the motivations of the system break down. So, just how different is this? Presumably on a conceptual basis you want your universities to be able to teach about things invented in the last 20 years without licensing patents?

CHY872··on Capturing carbon from the air will always be expensive (2020)
Plants could also hit the amounts required. If worldwide, 10% of all farmland was used to grow bamboo, you'd be able to harvest enough carbon each year to cover the rest of the world's emissions. That's still a frighteningly large amount (really it's a frightening amount of agriculture that the world does) but given the supply chains that already exist for agriculture it's believable that it could be turned into a carbon sequestering supply chain.
CHY872··on Capturing carbon from the air will always be expensive (2020)
The mistake of this article is that it assumes that the cost of energy would be constant for such a large user of electricity. Firstly, the $0.07 industrial price for energy is driven by grid consumption. You're paying for some very cheap, bulk, steady usage production (e.g. nuclear), some very cheap but intermittent energy production like wind, and a lot of very expensive gas/coal production that can be turned on and off. If the load is extremely predictable, or the consumption can be switched off at various times, it should be possible to dramatically reduce the overall price of electricity.

For a simple example, it's usually assumed that installation of 1kW of solar power costs $1000 (of which $200 goes into the panel). Well located, it'll produce at least 5kWh per day over its lifespan of about 20 years. This would produce you power at 1/3 the rate quoted by the article. But, if you were installing thousands of such things, the labour would likely go down a huge amount, and the panels would, too. Imagine the panel costs the same and the labour costs $400 instead of $800. You'd suddenly be at about $0.01-0.02 per kWh.

Let's take this further. Imagine you laid down a 100km/100km area with solar panels - every inch, and somehow you could feed that into your CO2 vacuum cleaner. This would cost you about $50B/year to build and then maintain, but after 20 years you'd have a (average) 2TW power station.

Let's say that sounded like too much work, and you wanted to go nuclear instead. It's claimed a new nuclear power station costs about $5k per kilowatt. That would cost a _lot_ more to build - $160B per year of expenditure to build up over 60 years and not 20 - but the result is the same, you'd have a 2TW power station. Arguably with a nuclear power station, if you were building a really big one, you'd use the same designs and it'd get much cheaper as a consequence.

According to the calculations in the article, that would be enough (with the carbon vacuum cleaner) to suck up about 1.5 megatonnes of CO2 per hour, or roughly the same amount as the US produces each year.

It'd be a frighteningly complex project, but at least the cost in terms of power alone comes out cheaper than covid or the Ukraine war, right?

CHY872··on New MacBook Air with M2
As a software engineer, the software is pleasant. I have a Unix OS for development tooling and the standard set of applications (browser, preview, file management, IDE tooling) just work. It seems far more likely that something works first time than my desktop that runs either Windows or Linux (Windows example: clock somehow ends up 1 hour out of sync every week or two, computer sometimes locks up leaving me no control over mouse, screen flickers whenever my VR headset comes out of sleep moode. Linux example: I now have to enter my password 3 times in order to fully get into the operating system). Mostly I'm disappointed with the hardware - my late-2018 model is extremely slow for what it is.
CHY872··on FedEx to close data centers, retire mainframes
Most large companies do at least some elements of multicloud. This may be as simple as doing ETL in AWS and then pushing the data over to BigQuery for dashboarding, it might be using all AWS and also Office365, it might be building applications which part run against Dynamo and part run against Cloud Spanner. It's also the case that the applications you run each year have some turnover rate. Maybe you're running Jira this year, maybe you're switching to Asana in a couple of years. Maybe over a 5 year period you're moving from Teradata to Snowflake. Which cloud env do you deploy Snowflake to?

Your negotiating power is then in the momentum of change. If GCP is working better for you than AWS right now, send your new spend to GCP where possible and where stuff is rotating out, move the new stuff to GCP. If you just got a good deal from Azure, start moving in that direction.

This is one of the 'big company vs small company' things, by the way - it doesn't make as much sense for a 100 person startup. But FedEx are a 300k employee juggernaut who spend $75B each year servicing $100B of revenue. They'll have a lot of tech in use.

CHY872··on Kubernetes is a red flag signalling premature optimisation
The advantage of K8s isn't really in the virtualization technique used, but in the orchestration it can be made to perform for you. You can for sure configure K8s to use a host per container, if this is what you want.

Example of thing that is pretty straightforward in K8s and much less straightforward outside of it.

1. For compliance reasons, you need to make sure that your underlying OS is patched with security updates.

2. This means you need to reboot the OS every X time.

3. You want to do this without downtime.

4. You have a replicated architecture, so you know you have at least two copies of each service you run (and each can handle the required traffic).

In K8s, this operation can be as simple as:

1. Mark your old nodes as unschedulable.

2. Drain your old nodes (which will grab new nodes from your cloud provider, installing the updated machine image).

3. Delete your old nodes.

The exact steps will differ based on your use case, but that's basically it.

Steps you didn't need to think about here:

1. If I'm about to take a node down, do I have enough redundancy to handle its loss? K8s understands the health of your software, and you have a policy configured so it understands if taking down a container will cause an outage (and avoid this). Note: third party tech will be naturally compatible - if you use Elastic's cloud-on-k8s operator to run ES, it'll appropriately migrate from host to host too, without downtime. Likewise, the same script will run on AWS, Azure, GCP.

2. How fast can I run this? If building this logic yourself, you'll probably run the upgrade one node at a time so as to not have to think about the different services you run. But if it takes 15 minutes to run a full upgrade, you can now only upgrade 100 hosts each day. K8s will run whatever it can, as soon as it can without you having to think about it.

3. What happens if concurrent operations need to be run (e.g. scale-up, scale-down)? With K8s, this is a perfectly reasonable thing to do.

4. Does this need to be monitored? This is a fairly standard K8s workflow, with most components identical to standard scale-up/scale-down operations. Most components will be exercised all the time.

Generally I've been impressed by how straightforward it's been to remove the edge cases, to make complex tech fit well with other complex tech.

A while back we upgraded between two CentOS versions. In such a case it's recommended to reinstall the OS - there's not a clear upgrade path. In K8s, this would have been the same set of steps as the above. In many orgs, this would be a far more manual process.

CHY872··on The Pentagon uses a secret program to wage proxy wars
Generally, the result of US diplomacy and projection of power over the last 50-75 years has been hugely beneficial and highly cost effective for the US. Why does anyone invest in anything? Because they want to see a return. The US has seen this in spades, as have (in general) its allies.

You can see this right now in Ukraine. The US and its allies are busy donating/selling all of their soon-to-expire weapons, their older model (but still good) jets, their brand new weapons. Who benefits from this? Ukraine, now. But also the weapon manufacturers, who represent a non-trivial proportion of the US economy. If Ukraine wins the war, it will be paying off its debts to the US for a century, with interest.

An economic example might be the sanctions it placed on Russia along with its allies. Russia is currently forecasted to see a 20% drop in its GDP this year, probably the single biggest effect of the war (compare to Iraq, Afghanistan, Syria effects on the US). Lots of the sanctioning can only be done because most of the global economy runs on the US dollar, as opposed to the yuan, yen, pound, euro, because the Russian loans are dollar denominated. If someone's putting the pressure on the US in some way, its various investments let it wield some massive clubs.

CHY872··on Formula One’s sharpest car designer is also its master of loopholes
The early ones are smaller than you think. The Leyton House car he designed is about 4.4m long, 2.1m wide, and about 1m tall, sitting the top of the driver's head about 70cm off the ground. The current ones are ginormous in comparison, about 5.5m long, 2m wide. https://i.ytimg.com/vi/DY0LvauM3Gw/maxresdefault.jpg
CHY872··on What will a Chromium-only Web look like?
This isn't a competition for 'most secure' necessarily. Rather, simply reducing the surface area for attack is positive from a security perspective. If there's some vulnerability in iOS that come from being able to make pages executable, if you only have Safari JIT-ing you have to find a bug in Safari, or the app store review process (and get the user to download your app). If iOS runs Chrome as well, you can find a bug in _either_ Safari _or_ Chrome.

While that's just Safari and Chrome, that's probably ok. But what happens when it's Safari, Chrome, Firefox, Opera, Brave, etc, etc?

For the security test, there are various ways that an org builds software with integrity, and it's the sort of thing that requires a huge amount of effort to get right. Standards like FedRAMP, SOC2, ISO9001, etc etc are the sorts of standardized things that exist (containing things like 'all code must be reviewed'). I think for a browser, if you were Apple and were looking to accept other browser partners, you'd likely do something like this; regular audits of quality, requirements that must be met to maintain access, pentests, basically a continuous process that's to be met by the supplier (similar to how hardware suppliers must meet many requirements).

CHY872··on US moves closer to recalling Tesla’s self-driving software
Apple are down 26% ytd. It wouldn’t be unheard of in this market. What should hopefully be clear is that stocks such as Tesla are not particularly correlated to the fundamentals of the company, there are whole-economy effects driving price rises and drops.

What I see in Tesla: - extremely profitable car manufacturing. industry beating profits per car driven by cheaper BOM than legacy manufacturers, in large part due to innovation. margin of 30.5%. - Manufacturing limited - huge wait list despite accelerating production (Q1 2022 best quarter ever, 68% increase yoy). - huge investments in manufacturing across the supply chain starting to pay off. - for the first time, manufacturing investments that can rival premium legacies. With the factories in Berlin and Texas coming online, it’s believable that Tesla has capacity to produce in excess of a manufacturer like BMW. - very high purchaser satisfaction (the product is good). - large overall profit - already beating most in the industry.

CHY872··on Fork() without exec() is dangerous in large programs (2016)
So the problem is what happens to the old and new processes after the fork. To CoW, you need to mark all the pages read only in _both_ old and new which means that every memory write in the caller will now pagefault since the OS now has to lazily copy on both sides. So with true copy on write the fixed costs may be low but the marginal cost per memory write may be high in both parent and child. In this case you can see why the resident set is copied, yes? It’s the smallest amount of memory that guarantees predictable performance subsequent to the call returning.
CHY872··on Electric vehicle battery capable of 98% charge in less than ten minutes
Yeah no. GP is arguing that most people should not buy an electric car for a reason that's invalid for the 99th percentile of people, and saying that it's too expensive to install a solution that is not what you need to make an electric car viable.

I can go buy a $50k top of rack switch to route data between my WiFi APs, yes, and I might want to! But it's not valid to then go around telling people that they're not ready for multiple access points because the tech to link them costs $50k. And it's certainly not 'arrogant' to correct people of their misconceptions, because this is a huge EV misconception.

CHY872··on What I miss in Java, the perspective of a Kotlin developer
For some of this stuff, there are compiler extensions that allow extra type checking to be added e.g. Google Error-Prone: https://github.com/google/error-prone with stuff like: https://errorprone.info/bugpattern/ReturnMissingNullable.

Doesn't help you with third party libraries, but across an org applying that rule (and others!) typically ensures some consistency.

CHY872··on SIMD accelerated sorting in Java – how it works and why it was 3x faster
Also, the JVM can frequently totally avoid compiling large swaths of the code (my methods ended up with about 10 uncommon traps in each method). https://shipilev.net/jvm/anatomy-quarks/29-uncommon-traps/
CHY872··on SIMD accelerated sorting in Java – how it works and why it was 3x faster
It would not be hard to write a quicksort which could be automatically vectorized. For example, this is a perfectly valid partition implementation of the pivot operation.

    int partition(int[] array, int from, int to, int pivot) {
        int[] buf1 = new int[to - from];
        int[] buf2 = new int[to - from]; // buffers could be preallocated, as in the blogpost

        int idx1 = 0;
        int idx2 = 0;

        for (int i = from; i < to; i++) {
            int value = array[i];
            if (value < pivot) {
                buf1[idx1++] = value;
            }
        }

        for (int i = from; i < to; i++) {
            int value = array[i];
            if (value >= pivot) {
                buf2[idx2++] = value;
            }
        }

        System.arraycopy(buf1, 0, array, from, idx1);
        System.arraycopy(buf2, 0, array, from, idx2);
    }

It would be relatively straightforward for a compiler to automatically vectorize the two loops I've coded up. I don't know if there's one that would, but with the vpcompress instruction I think the absence of a compiler doing it automatically would simply be a function of it not being a common use case.
← PreviousPage 3 of 18Next →