Saturday, April 1, 2023

A New Beginning for LifeHacker

When I was a teen, I became the kid who transferred schools. You know the type: someone who lived in transition, changing schools, neighborhoods, and friends often. At its worst, I changed high schools five times in three years. And like many things at that age, the transfers were for reasons out of my control.

I had two revelations during those years when I was learning about both who I was and wanted to be. The first was that each move was a chance at reinvention. The second was that no matter my goals for who I wanted to be, I would be a product of my setting. Whether I liked it or not, the opportunities I had—and my potential to seize them—would be meaningfully influenced by my setting. For better or worse, who I was would be partly the result of what was around me.

This month, Lifehacker was sold from G/O Media to Ziff Davis.

Some of the changes have been immediate. If you’re a regular reader, for example, you may have noticed that Lifehacker stopped publishing slideshows. Slideshows were a reality of our previous context, whether I liked it or not. (I did not.) Those in-line ads are gone, too.

After seeing our site free of its usual glut of ads, one editor said, “I want to cry.” It was a joke, but also it wasn’t.

Another editor said, “Whoa, the page just...loads. And then after each paragraph of text is another paragraph of text.”

If you don’t work in digital media or live on the internet, you might find those things unremarkable. But to us, they’re huge UI improvements that make our stories look better and read more clearly.

Other changes will be longer term but will follow the same logic of eliminating slideshows and publishing things like the Home Remedy Handbook by Senior Health Editor Beth Skwarecki, which we were proud to publish earlier this month. We want to focus on thoughtful, challenging, and entertaining advice to build a relationship with our more loyal readers while also welcoming new ones.

Slideshows, ads, and thinly-veiled SEO grabs will continue to be a reality in the shrinking landscape of free journalism. I don’t see fixes to those problems on the horizon—frankly, after countless media layoffs recently I feared that Lifehacker was being closed to cut costs instead of being acquired—but my goal is to make Lifehacker the best it can be within that landscape.

A recent comment from Kinja user Blaine summarized my hopes when they said, “This is among the best and most informative writing I’ve seen on Lifehacker or any similar outlet, bar none. Thank you.”

Speaking of Kinja, Lifehacker’s new home will also mean a shift to a new platform. Lifehacker may look a little different in the coming months, but most changes should be either negligible or clear improvements for readers.

The change will also be a turning point for our comments section, which sometimes reflects the toxicity and bad-faith reactions that are common in anonymous, unmoderated forums. Allowing those comments was my failure: I ignored them and often expected my writers to do the same, and allowed more bullying and abusive language than I should have. I’m eager to fix that in the future with a comments policy that has zero tolerance for personal attacks, insults, and general hate-reading. Our community won’t be for those who visit for little reason other than to pick fights.

You can expect to hear from me more, too. The Lifehacker team knows me well, but our readers less so—mostly because I rarely write for the site and generally limit my Twitter profile to posting about comics, video games, or my book. But I should be a more willing and visible face of the brand that I love so much. (If you really want to get to know me and the worldview I bring to Lifehacker, you can read my book.)

It’s a new beginning for Lifehacker, and an opportunity for reinvention. Much of it will be in our control. Some of it won’t. But I’m confident that Lifehacker’s new business home will be more conducive to the site I want us to be. Regardless, I love a lofty goal: to give some of the best and most informative content that you can find on the internet.



from Hacker News https://ift.tt/xDfiGg3

Friday, March 31, 2023

“Advice to Bride and Groom” by Plutarch (C. 100 CE)

When the London newspaper the Athenian Mercury, edited and published by the author and bookseller John Dunton, first answered questions about romance, bodily functions, and the mysteries of the universe in 1691, it may have created the template for the advice column. But the history of advice stretches back even further into the past. Advice—whether unsolicited, unwarranted, or desperately sought—appears in ancient philosophical treatises, medieval medical manuals, and countless books. Lapham’s Quarterly is exploring advice through the ages and into modern times in a series of readings and essays.

Several of the Plutarch works collectively known as Moralia resemble advice columns at times. The Roman historian and philosopher had thoughts on how to educate children, how to tell a true friend from an untrustworthy flatterer, and how a young man should properly study poetry. And he has some advice for the newlywed.

“Advice to Bride and Groom” includes forty-eight lessons on marriage, much of it aggregated from earlier thinkers, that he presented to students after they married. “Plutarch finds less to criticize and fewer potential problems in the husband’s behavior,” scholar Sarah B. Pomeroy noted in a 1999 essay on the work. Instead he concentrated his “advice on training the wife to be a congenial and productive marital partner who is willing to accommodate herself to her husband’s wishes. We must conclude that in the area of marital relations Plutarch was not an original thinker, but rather an industrious and eclectic one.”

 

In music they used to call one of the conventional themes for the flute the “Horse Rampant,” a strain that, as it seems, aroused an ardent desire in horses and imparted it to them at the time of mating. Of the many admirable themes contained in philosophy, that which deals with marriage deserves no less serious attention than any other, for by means of it philosophy weaves a spell over those who are entering together into a lifelong partner­ship and renders them gentle and amiable toward each other. I have therefore drawn up a compendium of what you, who have been brought up in the atmosphere of philosophy, have often heard, putting it in the form of brief comparisons that it may be more easily remembered, and I am sending it as a gift for you both to possess in common; and at the same time I pray that the muses may lend their presence and cooperation to Aphrodite and may feel that it is no more fitting for them to provide a lyre or lute well attuned than it is to provide that the harmony which concerns marriage and the household shall be well attuned through reason, concord, and philosophy. Indeed, the ancients gave Hermes​ a place at the side of Aphrodite in the conviction that pleasure in marriage stands especially in need of reason; and they also assigned a place there to persuasion and the graces, so that married people should succeed in attaining their mutual desires by persuasion and not by fighting and quarrelling.

—Solon​ directed that the bride should nibble a quince before getting into bed, intimating, presumably, that the delight from lips and speech should be harmonious and pleasant at the outset.

—In Boeotia, after veiling the bride, they put on her head a chaplet of asparagus; for this plant yields the finest flavored fruit from the roughest thorns, and so the bride will provide for him who does not run away or feel annoyed at her first display of peevishness and unpleasantness a docile and sweet life together. Those who do not patiently put up with the early girlish disagreements are on a par with those who on account of the sourness of green grapes abandon the ripe clusters to others. Many newly married women get annoyed at their husbands because of their first experiences, and find themselves in like predicament with those who patiently submit to the bees’ stings but abandon the honeycomb.

—Especially in the beginning, married people ought to be on their guard against disagreements and clashes, for they see that such household vessels as are made of sections joined together are at the outset easily pulled apart by any fortuitous cause, but after a time, when their joints have become set, they can hardly be separated by fire and steel.

—Just as fire catches readily in chaff, fiber, and hares’ fur but goes out rather quickly unless it gets hold of some other thing that can retain it and feed it, so the keen love between newly married people that blazes up fiercely as the result of physical attractiveness must not be regarded as enduring or constant unless, by being centered about character and by gaining a hold upon the rational faculties, it attains a state of vitality.

—Fishing with poison is a quick way to catch fish and an easy method of taking them, but it makes the fish inedible and bad. In the same way, women who artfully employ love potions and magic spells upon their husbands, and gain mastery over them through pleasure, find themselves consorts of dull-witted, degenerate fools. The men bewitched by Circe were of no service to her, nor did she make the least use of them after they had been changed into swine and asses, while for Odysseus, who had sense and showed discretion in her company, she had an exceeding great love.

—Men who through weakness or effeminacy are unable to vault upon their horses teach the horses to kneel and crouch down. In like manner, some who have won wives of noble birth or wealth, instead of making themselves better, try to humble their wives, with the idea that they shall have more authority over their wives if these are reduced to a state of humility. But as one pays heed to the size of his horse in using the rein, so in using the rein on his wife he ought to pay heed to her position.

—Whenever the moon is at a distance from the sun we see her conspicuous and brilliant, but she disappears and hides herself when she comes near him. Contrariwise, a virtuous woman ought to be most visible in her husband’s company and to stay in the house and hide herself when he is away.

—Herodotus was not right in saying​ that a woman lays aside her modesty along with her undergarment. On the contrary, a virtuous woman puts on modesty in its stead, and husband and wife bring into their mutual relations the greatest modesty as a token of the greatest love.

—Whenever two notes are sounded in accord the tune is carried by the bass; and in like manner every activity in a virtuous household is carried on by both parties in agreement but discloses the husband’s leader­ship and preferences.

—Cato expelled from the senate​ a man who kissed his own wife in the presence of his daughter. This perhaps was a little severe. But if it is a disgrace (as it is) for man and wife to caress and kiss and embrace in the presence of others, is it not more of a disgrace to air their recriminations and disagreements before others and, granting that his intimacies and pleasures with his wife should be carried on in secret, to indulge in admonition, fault-finding, and plain speaking in the open and without reserve?

—Just as a mirror, although embellished with gold and precious stones, is good for nothing unless it shows a true likeness, so there is no advantage in a rich wife unless she makes her life true to her husband’s and her character in accord with his. If the mirror gives back a gloomy image of a glad man or a cheerful and grinning image of a troubled and gloomy man, it is a failure and worthless. So, too, a wife is worthless and lacking in sense of fitness who puts on a gloomy face when her husband is bent on being sportive and gay and again, when he is serious, is sportive and mirthful. The one smacks of disagreeableness, the other of indifference. Just as lines and surfaces in mathematical parlance have no motion of their own but only in conjunction with the bodies to which they belong,​ so the wife ought to have no feeling of her own, but she should join with her husband in seriousness and sportiveness and in soberness and laughter.

—Men who do not like to see their wives eat in their company are thus teaching them to stuff themselves when alone. So those who are not cheerful in the company of their wives, nor join with them in sportiveness and laughter, are thus teaching them to seek their own pleasures apart from their husbands.

—The lawful wives of the Persian kings sit beside them at dinner and eat with them. But when the kings wish to be merry and get drunk, they send their wives away and send for their music girls and concubines.​ They are right in what they do, because they do not concede any share in their licentiousness and debauchery to their wedded wives. If therefore a man in private life, who is incontinent and dissolute in regard to his pleasures, commits some peccadillo with a paramour or a maidservant, his wedded wife ought not to be indignant or angry, but she should reason that it is respect for her which leads him to share his debauchery, licentiousness, and wantonness with another woman.

—Kings fond of the arts make many persons incline to be artists, those fond of letters make many want to be scholars, and those fond of sport make many take up athletics. In like manner a man fond of his personal appearance makes a wife all paint and powder, one fond of pleasure makes her meretricious and licentious, while a husband who loves what is good and honorable makes a wife discreet and well-behaved.

—A wife ought not to make friends of her own but enjoy her husband’s friends in common with him. The gods are the first and most important friends. It is becoming for a wife to worship and to know only the gods that her husband believes in, and to shut the front door tight upon all queer rituals and outlandish superstitions. For with no god do stealthy and secret rites performed by a woman find any favor.

—Helen was fond of wealth and Paris of pleasure; Odysseus was sensible and Penelope virtuous. Therefore the marriage of the latter pair was happy and enviable, while that of the former created an “Iliad of woes” for Greeks and barbarians.

—The Roman,​ on being admonished by his friends because he had put away a virtuous, wealthy, and lovely wife, reached out his shoe and said, “Yes, this is beautiful to look at, and new, but nobody knows where it pinches me.” A wife, then, ought to rely not on her dowry or birth or beauty but on things in which she gains the greatest hold on her husband, namely conversation, character, and comrade­ship, which she must render not perverse or vexatious day by day but accommodating, inoffensive, and agreeable. For, as physicians have more fear of fevers that originate from obscure causes and gradual accretion than of those that may be accounted for by manifest and weighty reasons, so it is the petty, continual, daily clashes between man and wife, unnoticed by the great majority, that disrupt and mar married life.

 

Read the previous entries in this series: Inez Milholland and Eugen Boissevain and George Washington.



from Hacker News https://ift.tt/JbZzMDh

Bouguer’s Halo

What is so special about Bouguer's halo?

Fogbows and 22° halos are relatively common.  Why is their simultaneous appearance remarkable?   Fogbows are produced when small fog droplets (5 to 50 micron diameter) refract, reflect and diffract sunlight.  In this sighting the droplets were supercooled.  Ice halos are from the refracted and reflected light from quite large (100 to 1000 micron) ice crystals.

The Bouguer’s halo rarity comes because water droplets and ice crystals cannot co-exist in a stable mixture except at one** unique temperature and pressure, the 'triple point' at 0.01 C and 6.1 mbar. Above zero, ice is unstable. Below zero water droplets are unstable. Thermodynamically, a natural long-lived Bouguer halo from a water drops and ice mixture is an impossibility.
 
At subzero temperatures water droplets can remain in a metastable state if there are no significant surfaces or nuclei onto which water vapour can condense into ice.   But when nuclei are introduced the transformation from a supercooled water fog into diamond dust ice crystals is sudden.    The vapour pressure of ice is less than that of supercooled water and so water drops evaporate while ice crystals grow rapidly.    This sudden phase change is responsible for hole-punch clouds and their trailing virga of halo forming ice crystals.

Marko Riikonen writes: “My experience from Finland is that you either have fog or diamond dust. On the two occasions I have seen a display where fogs and diamond dusts passed and the moments when halos and fogbow were seen at the same time lasted just seconds. In photos these mostly show up together only because the time exposure had captured both fog and diamond dust stages on film.

In the first case the diamond dust and fog were too thick to let the moon shine through. In the second the sky was overcast. This latter type of occurrence if rather rare - you don't often have diamond dust of fog under cloud cover.”


Ed Stockard comments on the plume at far right, top image, could it have introduced the water droplets that formed the fogbow?  "On this day I am quite certain the answer is no. The plume is from our generator exhaust and is a fair amount north of the fogbow.  I also think if this were the case we would have seen it before now. I had thought about this as well."

** To be pedantic, there are other triple points in the water-ice system but they are at pressures way above those in our atmosphere.



from Hacker News https://ift.tt/YEg46w9

The same Italian regulator who banned ChatGPT has a non GDPR-compliant website

Failure to comply with GDPR may result in a fine of up to 4% of the annual turnover. It is defined in article 12 of the Regulation. To get more, please read the GDPR on the EU website



from Hacker News https://ift.tt/5PzShQy

How the EU CHIPS Act Could Build “Innovation Capacity” in Europe

The European Commission wants Europe to boost its share of global semiconductor production to 20 percent by 2030, from 10 percent today. To that end, it is forwarding plans for more than €43 billion in public and private investment through a European Chips Act. To accomplish that increase in chip capacity, the legislation will approve appropriations for R&D, incentivize manufacturing, and take steps to make the supply chain more secure. Jo De Boeck, chief strategy officer and executive vice president at the Belgium-based nanoelectronics R&D center Imec, explained a proposed R&D structure and its likely impact to engineers at the 2023 IEEE International Solid State Circuits Conference (ISSCC) last month in San Francisco. The R&D segment relies on the establishment of advanced pilot line facilities, to enable a path from laboratory breakthrough to fab production, and a network of competence centers, to build up capacity for semiconductor design. De Boeck spoke with IEEE Spectrum’s Samuel K. Moore at ISSCC.

IEEE Spectrum: What would you say are Europe’s strengths today in semiconductor manufacturing?

Jo De Boeck: Well, manufacturing holds quite a few things. So first and foremost, I think of semiconductor manufacturing equipment and materials. Think of [Netherlands-based extreme-ultraviolet lithography maker], ASML. If you move up to the manufacturing part, you have some of our integrated device manufacturers [IDMs] in analog and analog mixed-signal and power devices, which is, of course, quite a very important area of devices and production to be in. But clearly—and that’s part of the reason for the Chips Act—there’s no European manufacturing presence at the most advanced technology nodes.

.

That said, how much of the focus should be on getting that cutting-edge logic versus building on the strengths that you already have?

De Boeck: Well, if it means focusing on one is losing on the other, I think that’s a bad choice to make. I think it’s important, first of all, to keep a long enough view in mind. 2030 is like tomorrow in this industry. So if we’re looking at getting 20 percent production in Europe by 2030 and you would aim that toward being leading edge, you’re in a hard place already. Before fabs are built and technology is transferred, it will be close to the end of the decade. So we need to look further out whilst continuing to build on the strengths that are there, such as the IDMs that are producing the goodies that we just discussed.

I think the important part is to find a way to keep up the capacity of the R&D and to start training people on the design of the leading-edge nodes. If there’s no demand [from chip-design firms], there will be no economical reason to build a fab [in Europe].

You talked about building “capacity to innovate.” Could you just start by explaining what’s meant by that?

De Boeck: The capacity for innovation in the case of our industry means two things—the design and the technology. And they need to go hand in hand. They need to be really close to each other. One area of the capacity will be on the design platform, and that design platform will be in the cloud, accessible from many places. The idea is that there will be design capacity in each and every member state through competence centers.

The design capacity is then balanced by the innovation in semiconductor technology. That will be carried out in larger facilities, because there needs to be focused investments there. These will be connected to competence centers for specific expertises and for design enablement on a pilot line. So the pilot line/competence center combination is the innovation capacity.

You also mentioned virtual prototyping as part of the plan. Please explain what you mean by that and what its role is.

De Boeck: I can explain by the example of back-side power delivery network technology. [Ed: This is a technology expected to debut in two or three years that delivers power to transistors from beneath the silicon instead of from above as is done now.] It’s something where the design community needs to get its hands on to do system-level exploration to see how, for instance, a back-side power distribution network could help the performance of a circuit improve. All of this requires this interplay between technology, electronic design automation vendors, and the design community. This has to be done first at a modeling and virtual prototyping phase, before you can make full silicon.

You stressed the importance of full-stack innovation. Please explain.

De Boeck: Full-stack means different things to different disciplines. But take, for example, the interplay between sensing and compute in the car of the future. That, of course, will involve a high-performance computer that needs to talk to the environment whether we’re talking to the other traffic elements—pedestrians, bicycles, cars, etc.—or understanding weather conditions That will require a lot of sensors in the car whose data must be fused by the computer. If you don’t know how this data will enter the sensor fusion engine, how much preprocessing you want to do on the sensor, you may be focusing on a suboptimal solution when developing your sensor or system architecture. Maybe you need to have a neural network on your radar to convert the raw data to early information before sending it to the central engine where it’s going to be combined with the camera input and whatever else is needed to build a full picture around the car or in its environment. A situation like that will require every element of that full stack to be co-optimized.

How can the EU Chips Act actually help make that happen?

De Boeck: Well, I think in general terms, it could stimulate collaboration. It could help to create awareness and start training people in this context because you need youngsters to start looking at the challenges in this particular way.

From Your Site Articles

Related Articles Around the Web



from Hacker News https://ift.tt/iYIzcvb

Virgin Orbit: Sir Richard Branson's rocket company lays off 85% of staff

"We have no choice but to implement immediate, dramatic and extremely painful changes," Virgin Orbit chief executive Dan Hart said at a meeting with employees, according to CNBC, which first reported the news.



from Hacker News https://ift.tt/GRDJoW7

Decreasing the Number of Memory Accesses 1/2

We at Johnny’s Software Lab LLC are experts in performance. If performance is in any way concern in your software project, feel free to contact us.

When we are trying to speed up a memory-bound loop, there are several different paths. We could try decreasing the dataset size. We could try increasing available instruction level parallelism. We could try modifying the way we access data. Some of these techniques are very advanced. But sometimes we should start with the basics.

One of the ways to improve on memory boundness of a certain piece of code is the old-fashioned way: decrease the total number of memory accesses (loads or stores). Once a piece of data is in the register, using it is very cheap, to the point of being free (due to CPU’s ability to execute up to 4 instructions in a single cycle and their out-of-order nature). So all techniques that try to lower the total number of loads and stores should result in speedups.

Techniques

Like what you are reading? Follow us on LinkedIn , Twitter or Mastodon and get notified as soon as new content becomes available.
Need help with software performance? Contact us!

Loop Fusion

If we have two consecutive loops that operate on the same dataset, fusing them into one loop would decrease the number of memory loads and stores and consequently improve performance. This transformation is called loop fusion or loop jamming. Consider the example of finding a minimum and maximum in an array. One of the ways to do it is using two separate loops:

double min = a[0];

for (int i = 1; i < n; i++) {
    if (a[i] < min) { min = a[i] };
}

double max = a[0];

for (int i = 1; i < n; i++) {
    if (a[i] > max) { max = a[i] };
}

Both loops touch process the same dataset. We could merge the two loops into one loop that finds both minimum and maximum. This cuts the number of data loads by two.

double min = a[0];
double max = a[0];

for (int i = 1; i < n; i++) {
    if (a[i] < min) { min = a[i] };
    if (a[i] > max) { max = a[i] };
}

We measure the effect of loop fusion in the experiments section.

A few notes about loop fusion:

  • Loop fusion is also a compiler optimization technique, so in theory the compiler can do it automatically. But this doesn’t happen often and when it does happen, this optimization has a tendency to break easily.
  • With regard to loop fusion, there are cases where loop fusion would fail to deliver speed improvements. If one or both loops are vectorized before the fusion, but the fused loop is not vectorized, then this transformation can result in a slowdown, not a speedup.
  • Loop fusion is a close relative of loop sectioning. The main difference is that loop fusion reuses the data while it is in registers, whereas loop sectioning reuses the data while it is in fast data caches. Therefore, a loop fusion is more memory efficient that loop sectioning, but fusing two loops is more complex than sectioning two loops. Also, preserving vectorization is easier with loop sectioning.

C++ Ranges

For folks using C++ STL algorithms, it is important to be aware of C++ ranges. The original STL library contains many algorithms, but they are not composable. Composability means that the result of one algorithm is fed into another algorithm. Consider the example:

struct user_t {
   int id;
   std::string name;
   int age;
};

std::vector<int> get_ids_adult_users(std::vector<user_t>& users) {
    std::vector<user_t> adult_users;
    std::copy_if(std::cbegin(users), std::cend(users), std::back_inserter(adult_users), [](auto const& user) { return user.age >= 18; });
    std::vector<int> ids;
    std::transform(std::cbegin(adult_users), std::cend(adult_users), std::back_inserter(ids), [](auto const& user){ return user.id; });
    return ids;
}

The function get_ids_adult_users returns the vector containing the ids of all the users who are adults, i.e. whose age is 18 or more. To achieve this using STL, we use two algorithms: std::copy_if which filters out the minor users to create the list of adult users and std::transform to extract only ids from the vector of user_t class.

This approach forces the code to iterate the two collections instead of one: the first collection is the original collection of users, and the second collection is the temporary collection holding adult users. To avoid this, C++ developers have STL ranges at their disposal. Here is the same example rewritten using ranges:

std::vector<int> get_ids_adult_users(std::vector<user_t>& users) {
    auto ids = users | std::views::filter([](auto const& user){ return user.age >= 18; })
                     | std::views::transform([](auto const& user){ return user.id; });
    return {ids.begin(), ids.end()}
}

This code, apart from being cleaner, also performs fewer memory loads and memory stores. The filter adapter performs the filtering, and the result of filtering is directly fed into the transform adapter, element by element. This avoids running through the vector two times, and it is equivalent to loop fusion.

Kernel Fusion

Kernel Fusion is just loop fusion brought to a much higher level. Consider the following: imagine you have N image processing algorithms making an image processing pipeline. The output of algorithm X is the input of algorithm X+1. One of the ways to implement the pipeline is to have them run one after another, from zero to N-1. Each algorithm must finish before the next one starts.

With this kind of setup, processing an image will often be memory inefficient. The whole image is loaded from the slower parts of the memory subsystem to CPU registers, processed, then the output is written back to the memory subsystem. And this is repeated for each algorithm in the pipeline: load input, do some modifications, store output.

In this example, each algorithm is a kernel. And by kernel fusion, we mean that two algorithms are fused. An algorithm X generates a single pixel, and feeds it directly to the algorithm X + 1, then to the algorithm X + 2, etc. The benefit of such an approach is that all relevant data never leaves the CPU, which avoids unnecessary data movements.

However, there are two problems with this approach:

  • Writing such a processing pipeline is not easy, and this task needs to be planned from day one. In fact, there is a special programming language, Halide, that is designed for writing fast and portable image and tensor processing codes.
  • The types of algorithms that would benefit from this approach must be memory bound, i.e. light in computation. Algorithms that are computationally intensive would benefit little or not at all, because computational bottleneck will hide the memory latency.

If you happen to know more about this topic, please leave a comment or send me an e-mail, I would like to know more as well (and also keep this post updated).

Like what you are reading? Follow us on LinkedIn , Twitter or Mastodon and get notified as soon as new content becomes available.
Need help with software performance? Contact us!

Loop Fusion inside a Loop Nest

Loop fusion inside a loop nest (also called unroll-and-jam) is a more advanced type of loop fusion, applicable to loop nests. The technique is simple to apply to many sorting algorithms, but not only them. Consider the selection sort algorithm. Here is the source code:

for (int i = 0; i < n; i++) {
    double min = a[i];
    int index_min = i;
    for (int j = i + 1; j < n; j++) {
        if (a[j] < min) {
            min = a[j];
            index_min = j;
        }
    }

    std::swap(a[i], a[index_min]);
}

The algorithm is very simple: in the i-th iteration, it scans the elements from i to n to find the smallest value, and puts the value in place a[i].

For loop fusion inside a loop nest, we need to unroll the outer loop two or more times to make the fusion potential explicit. Here is the selection sort algorithm, where the outer loop has been unrolled two times:

for (int i = 0; i < n; i+=2) {
    min = a[i];
    index_min = i;
    for (int j = i + 1; j < n; j++) {
        if (a[j] < min) {
            min = a[j];
            index_min = j;
        }
    }

    std::swap(a[i], a[index_min]);

    min = a[i + 1];
    index_min = i + 1;
    for (int j = i + 2; j < n; j++) {
        if (a[j] < min) {
            min = a[j];
            index_min = j;
        }
    }

    std::swap(a[i + 1], a[index_min]);
}

The first and second inner loops are iterating over almost identical datasets. There are a few statements preventing a simple loop fusion, but they can be moved away. With some tricks, we fused together the two inner loops. Here is the result:

for (int i = 0; i < n; i+=2) {
    min_1 = a[i];
    min_2 = a[i + 1];
    index_min_1 = i;
    index_min_2 = i + 1;

    // min1 must be smaller than min2
    // Swap two values if not true
    if (min2 < min1) {
        std::swap(min1, min2);
        std::swap(index_min_1, index_min_2);
    }

    // Look-up two smallest values in array.
    // The smaller is kept in min1, the larger
    // in min2.
    for (int j = i + 2; j < n; j++) {
        if (a[j] < min_2) {
            if (a[j] < min_1) {
                min_2 = min_1;
                index_min_2 = index_min_1;
                min_1 = a[j];
                index_min_1 = j;
            } else {
                min_2 = a[j];
                index_min_2 = j;
            }
        }
    }

    std::swap(a[i], a[index_min_1]);
    std::swap(a[i + 1], a[index_min_2]);
}

The loop fusion in this case is not trivial, but it is possible. The inner loop is looking up the two smallest values in the array to put them into the beginning of the section currently being processed. The total number of memory accesses is about two times lower compared to the simple selection sort algorithm.

Note: This optimization closely resembles outer loop vectorization, where the outer loop is running several instances of the inner loop in parallel.

Decreasing the Number of Data Passes by Doing More Work

As we have seen in previous examples, loop fusion allows the elimination of some memory accesses by fusing two neighboring loops running over the same data. But this is not the only way. Many ideas that decrease the number of data passes will result in fewer memory accesses and better performance.

Consider the simple selection sort algorithm from the previous section. The original algorithm was looking for the minimum in the remaining array. To decrease the number of total memory accesses, we could scan for both minimum and maximum. We would then put the minimum element at the beginning of the remaining array and the maximum element at its end. The algorithm looks like this:

for (int i = 0, j = n - 1; i < j; i++, j--) {
    double min = a[i];
    int index_min = i;
    double max = a[j];
    int index_max = j;
    for (int k = i; k < j; k++) {
        if (a[k] < min) {
            min = a[k];
            index_min = k;
        }
        if (a[k] > max) {
            max = a[k];
            index_max = k;
        }
    }

    std::swap(a[i], a[index_min]);

    if (a[index_min] != max) {
        std::swap(a[j], a[index_max];
    } else {
        std::swap(a[j], a[index_min]);
    }
}

This version has fewer iterations, and therefore fewer memory loads, but inside each iteration it does twice as much work. From the algorithmic point of view, it performs roughly the same number of operations as the first version. But, performance-wise it is more efficient. In the experiments section we will see how much efficient.

Another important algorithm with a similar reduction in memory accesses is a variant of Quicksort called Multi-Pivot Quicksort. Before explaining MPQ, let’s give a quick reminder about Quicksort. The Quicksort algorithm consists of two steps. The first step is array partitioning: picking a pivot and then partitioning the array into a left part that is smaller than the pivot and a right part that is larger. The second step is the recursive call: the partitioning is performed recursively on the left and right part of the input array, until the size of the array becomes 1.

Recursive array partitioning in Quicksort

With Multi-Pivot Quicksort, the partitioning step is performed by picking two pivots and partitioning the array into three parts. Then partitioning is recursively performed on the left, middle and right part of the array. If an array has N elements, with plain Quicksort we expect an average number of memory accesses for each element of the array to be O(log2 N). With Multi-Pivot Quicksort, the average number of memory accesses would be O(log3 N).

Like what you are reading? Follow us on LinkedIn , Twitter or Mastodon and get notified as soon as new content becomes available.
Need help with software performance? Contact us!

Experiments

All the experiments were executed on Intel Core i5-10210U CPU, 4 cores, 2 threads per core. Each core has 32kB of L1i cache, 32kB of L1d cache and 256kB of L2 cache. There is a total of 6MB of L3 cache shared by all the cores. The source code used for all experiments is available here.

Loop Fusion

The first experiment is related to loop fusion. We measure the runtime of two separate loops and compare it with the runtime of the fused loop. The examples we use for testing are loops that calculate the min and max, first in two separate loops, then merged.

Here are the runtimes (five repetitions, average values):

Array Size Original Fused
32 kB Runtime: 0.159 s
Instr: 671 M
CPI: 0.793
Runtime: 0.068 s
Instr: 402 M
CPI: 0.665
256 kB Runtime: 0.136 s
Instr: 671 M
CPI: 0.800
Runtime: 0.068 s
Instr: 402 M
CPI: 0.667
2 MB Runtime: 0.136 s
Instr: 671 M
CPI: 0.801
Runtime: 0.068 s
Instr: 402 M
CPI: 0.667
16 MB Runtime: 0.171 s
Instr: 671
CPI: 0.855
Runtime: 0.085 s
Instr: 402 M
CPI: 0.739
128 MB Runtime: 0.175 s
Instr: 671 M
CPI: 0.855
Runtime: 0.086 s
Instr: 402 M
CPI: 0.742

The table shows, that, on average, the fused version is about two times faster than the original version. The fused version also executes less instruction and is more hardware efficient (Cycle per Instruction metric is better). Fewer instructions are executed because (1) there is only one loop instead of two, so this means fewer iterator increases, iterator comparisons, jumps and (2) removed one redundant load, since the piece of data is already in a register.

Selection Sort

We are going to experiment with selection sort, as described in the section about decreasing the number of data passes. To measure the effect we will compare the version of the selection sort where we are finding minimum only vs the version where we are finding both minimum and maximum. The first version scans the remaining part of the array to find the minimum and put it at the beginning. The second version scans to find both the minimum and maximum, and places them at the beginning and at the end of the array respectively. We expect the second version to be faster because it needs to perform two times fewer scans.

Here are the numbers (five runs, average numbers):

Array Size Only Min Min and Max
8 kB
16384 repeats
Runtime: 8.74 s
Instr: 60.3 B
CPI: 0.57
Runtime: 4.44 s
Instr: 43.2 B
CPI: 0.405
32 kB
1024 repeats
Runtime: 8.72 s
Instr: 60.1 B
CPI: 0.573
Runtime: 4.36 s
Instr: 43.0 B
CPI: 0.401
128 kB
64 repeats
Runtime: 8.69 s
Instr: 60.1 B
CPI: 0.572
Runtime: 4.37 s
Instr: 43.0 B
CPI: 0.402
512 kB
4 repeats
Runtime: 8.69 s
Instr: 60.1 B
CPI: 0.572
Runtime: 4.39 s
Instr: 42.9 B
CPI: 0.405

The Min and Max version is both faster and more hardware efficient in all cases. It also executes fewer instructions, because both the inner and the outer loops are shorter, so they perform fewer memory accesses.

Conclusion

Loop fusion is a simple and powerful technique to decrease the total number of memory accesses in the program. Although we described here the simplest version, loop fusion is possible even if datasets overlap partially.

In general, any idea that would result in a decrease of memory accesses has the potential to speed up your code. If you have any ideas that are not mentioned in this post, feel free to leave a comment so we can update this post.

In the next post we will talk about another way to decrease the total number of memory accesses. These memory accesses are “unwanted”, in the sense that the compiler has created them without your intention: memory accesses related to pointer aliasing and memory accesses related to register spilling. Until soon!

Like what you are reading? Follow us on LinkedIn , Twitter or Mastodon and get notified as soon as new content becomes available.
Need help with software performance? Contact us!



from Hacker News https://ift.tt/QxjdKCw