Uniplaces

uniplaces

In the ever-evolving landscape of computing, the quest for optimal performance has led to the exploration of parallelism — the art of breaking down complex tasks into smaller, manageable ones. At the heart of this pursuit lies the fundamental concept of threading, a powerful technique that enables programs to execute multiple tasks concurrently, unleashing the true potential of modern computing systems. Threading involves breaking a program into smaller, independently executable units called threads, running simultaneously to enhance efficiency and speed. This is one of the fundamental concepts of parallel programming. Before delving into the intricacies of threading, it’s essential to grasp the theoretical framework that underpins the world of parallel computing. Flynn’s Taxonomy, named after computer scientist Michael Flynn, provides a comprehensive classification system for parallel processing architectures. Understanding Flynn’s Taxonomy is crucial because it lays the foundation for comprehending the intricate relationships between threads, processes, and the overall structure of parallelized systems. A clear understanding of these concepts is essential for understanding how to create multi-threaded applications. This article marks the beginning of a blog series on multi-threading, covering all the theoretical and programming aspects of multi-threading. We’ll dig deep into threading APIs and libraries (POSIX Threads, C++ threads) and OpenMP in the upcoming blogs. Without further ado… Flynn’s Taxonomy In 1966 [ ], computer scientist Dr. Michael J. Flynn proposed a classification of computer architectures based on their capability to process the number of instruction streams and data streams concurrently. This classification is still relevant and known as Flynn’s taxonomy. 1 In his initial paper, Flynn proposed four classifications: Single instruction stream, single data stream (SISD) Single instruction stream, multiple data streams (SIMD) Multiple instruction streams, single data stream (MISD) Multiple instruction streams, multiple data streams (MIMD) Flynn published three further classifications of SIMD in a subsequent paper published in 1972[ ]: , , and . 2 Array Processors Pipelined processors Associative Processors “Stream” refers to the sequence of data or instructions as seen by the machine during the execution of a program. [ ] 1 A single stream issues one element in each time unit, resembling a queue. Conversely, multiple streams typically issue numerous elements per time unit, akin to managing multiple queues simultaneously. Consequently, a single instruction stream (SI) issues only one instruction within a time unit, whereas a multiple instruction stream (MI) issues multiple instructions during the same period. Similarly, a single data stream (SD) issues a single data element per time unit, while a multiple data stream (MD) issues multiple data elements within the same time frame. Flynn’s taxonomy can be visually represented as: Before proceeding, it's important to recall how instructions are executed (the so-called instruction cycle). The instruction cycle consists of following steps: Fetch instruction - read the instruction from the memory. Decode instruction - decode to interpret the requested action. Fetch Data (if needed) - get the data for processing the instruction. Execute instruction (process data) - execute the instruction/process the data. Write-back data - save/store the results. Let’s try to understand what these different classifications mean. Single instruction stream, single data stream (SISD) SISD represents a computing architecture where a uniprocessor machine executes a single instruction stream, operating on a single data stream. This architectural design corresponds with the principles of the von Neumann model. The control unit retrieves a sequence of instructions from memory, decodes them, and dispatches them to the processing unit, which handles the data fetched from memory one unit at a time. Consequently, only one instruction is executed at any given time, reflecting a sequential execution of instructions. It is crucial to note that SISD processors may exhibit limited concurrency. For instance, the execution phases of sequential instructions can overlap, facilitated by an additional functional unit. SISD processors achieve concurrent processing through techniques like * *or . pipelined superscalar processors Pipelined processors involve executing multiple instructions in the same execution unit concurrently by segmenting the execution unit into different phases, while superscalar processors execute multiple instructions in parallel using multiple execution units. Before the 2000s, most single-core processors adhered to the SISD architecture, encapsulating the foundational structure of early computing systems. Single instruction stream, multiple data streams (SIMD) In a SIMD system, a single instruction stream is broadcast to all the processing elements (PE), and each element independently processes its assigned portion of the data. This allows for efficient parallelization of tasks and can result in significant speedup for specific computations. SIMD is well-suited for tasks involving performing the same operation on a large data set in parallel, such as graphics processing, scientific simulations, or certain mathematical computations. An instruction is supplied to numerous data elements concurrently, following a synchronized execution pattern. All instructions are queued in this “lockstep” process, and the associated data is distributed across distinct compute units. Each compute unit executes the initial instruction in the queue simultaneously, proceeds to execute the subsequent instruction in sync, and continues this synchronized execution for following instructions in the queue. SIMD architecture finds its most prevalent application in Graphics Processing Units (GPUs). In 1972, Flynn published another research paper classifying SIMD into three further classifications: Array Processors (SIMT) An array (or vector) processor executes an instruction set optimized for efficiently processing large one-dimensional arrays called vectors. In this subtype of SIMD, each parallel processing element has its distinct memory and register file. However, they receive the same instructions. Nvidia’s concept, implemented in GPGPUs, is the most common example of array processors. SIMT combines SIMD with multi-threading and is the basis of most modern GPUs. SIMT (Single Instruction, Multiple Threads) Pipelined Processors (packed SIMD) Just like other SIMD variants, pipelined processors receive the same instructions. However, they read data from a central resource and process fragments of that data independently. Finally, they write back the results to the same central resource. Modern SIMD variations, such as Intel’s AVX or ARM’s NEON, use register files as the shared resource (instead of main memory). This register-based SIMD is commonly called , underscoring its efficient use of register files for parallel computation. packed SIMD Associative Processors (predicated/masked SIMD) Each parallel processing unit receives the same instruction, but the decision to execute or skip the instruction is made independently based on local data within the unit. Modern terminology characterizes this as “ ” or “ ” SIMD, showcasing the ability to conditionally execute operations based on specific criteria within individual processing units. Modern SIMD ISAs such as AVX-512 and GPGPUs use predication to improve cache usage efficiency and ensure effective pipelining. predicated masked Most modern GPUs utilize a combination of these methods, most commonly SIMT with predication. Multiple instruction streams, single data stream (MISD) In MISD systems, multiple instruction streams operate concurrently on a single data set. This type of architecture is less common than other categories in Flynn’s Taxonomy and is often considered more theoretical than practical. In an MISD system, different processors or processing elements receive distinct instructions, but they all operate on the same data stream. Each processor performs a unique computation on the shared data stream based on its assigned set of instructions. The results from each processor can be compared or combined to achieve a final output. One possible use case of MISD systems is creating fault-tolerant systems or specialized applications where redundant computations are performed simultaneously for error checking or reliability. For instance, some earlier MISD systems were designed for fault-tolerant space mission systems. Multiple instruction streams, multiple data streams (MIMD) In MIMD systems, multiple processors or processing elements operate independently, each with its own set of instructions and data. It is well-suited for applications that require parallelism on different tasks or where the workload can be divided into independent subtasks. MIMD systems are highly flexible and represent the most widely used class of computer architecture. Depending on how MIMD processors access the memory, they are classified into two categories: . Shared and distributed memory Examples Let’s try to understand these classifications using a simple example. Suppose we have two 1-D vectors, and , each having an equal number of single-precision floating-point numbers (floats). A B We have to multiply all the elements in A with a scalar and then add them to every corresponding element in B. The result must be stored in a third array called . c result Thus, we have: Vector A: [a1, a2, a3, ...]
Vector B: [b1, b2, b3, ...]
Scalar: c

result: [c * a1 + b1, c * a2 + b2, c * a3 + b3, ...] SISD For the given task, scalar addition and multiplication would involve processing each element of the vectors sequentially. The processor performs the addition of corresponding elements from the two vectors, followed by the multiplication with a scalar, and stores the results in a third vector. The operations are carried out one at a time. For example, iterating through every iteration of this for loop without any optimizations would be the SISD way of getting the vector. result for(int i = 0;  i < n; ++i){
  result[i] = c* A[i] + B[i];
} SIMD Suppose our machine supports Advanced Vector Extensions (AVX) SIMD instructions. Thus, a single SIMD register (YMM) can store 8 single-precision floats. Therefore, each element-wise operation is performed in parallel while using SIMD, enhancing efficiency. The same scalar addition and multiplication are applied to multiple elements concurrently. For example, let us assume we have n elements in A and B. We can perform 8 data operations simultaneously, significantly improving our efficiency. Only n%8 iterations will be done sequentially. In fact, those n%8 elements can also be efficiently performed using mask registers. For example, a C++ code using SIMD intrinsics can really do wonders. // SIMD code (with intrinsics)
int ub = n - (n % 8); // 8 floats per SIMD register
__m256 x, y, z, s, temp; // vectors of 8 float entries
s = _mm256_set1_ps(c); // store the scalar c
for(int i = 0;  i < ub; i += 8){ // notice the increment of 8
  x = _mm256_loadu_ps(&A[i]); // load 8 elements of A in x
  y = _mm256_loadu_ps(&B[i]); // load 8 elements of B in y
  z = _mm256_loadu_ps(&result[i]); // load 8 elements of result in z
  temp = _mm256_mul_ps(s, x); // multiply elements of A with s and store in temp
  z = _mm256_add_ps(temp, y); // add elements of temp with y and store in z
  _mm256_storeu_ps(&result[i], z); // copy the elements to the result vector
} 
 /* Reminder loop for remaining iterations
  * Masked registers can also be used instead of this
*/
for(int i = ub;  i < n; ++i){
  y[i] = a * x[i] + y[i];
} Don’t worry if all the SIMD jargon feels a bit heavy. SIMD intrinsics deserve an article of their own, and I’ll cover them in a future article. offers detailed documentation on how to use different intrinsics. Intel intrinsics guide Modern compilers also enable vectorization if the user gives relevant optimization flags. Feel free to check my article on to learn more about such compiler flags. Compiler Optimizations MIMD In MIMD, multiple processors operate independently, each executing its instructions on its data set. In the given task, different processors might perform various operations on different elements of the vectors simultaneously. Depending on the shared or distributed memory model, several ways exist to solve the given task. For instance, if working with a shared memory programming model like OpenMP, different threads may work together and distribute the loop iterations (See__ __). OpenMP scheduling Similarly, for a distributed memory programming model like MPI, the vectors may be distributed to different processors such that each calculates their respective chunk of result. One of the processors may work as a coordinator, distribute the data, and even collect the final result from all the processors. For example, if p processors exist, the data may be divided into chunks. n/p // Each processor works on n/p data elements
Processor 1: [c * a1 + b1, ....] -> Result1
Processor 2: [c * ae + be, ....] -> Result2 // e = n/p +1
Processor 3: [c * af + bf, ....] -> Result3 // f = 2*n/p + 1 What next? This brings us to the end of the first part of this blog series on multi-threading. In the next part, we’ll dig deep into SIMD and MIMD systems, mainly introducing the programming models used to exploit them. References [1] Very high-speed computing systems | IEEE Journals & Magazine | IEEE Xplore [2] Some Computer Organizations and Their Effectiveness | IEEE Journals & Magazine | IEEE Xplore [3] Intro to Parallelism with Flynn’s Taxonomy (youtube.com) Also published here. Featured Photo by on . JACQUELINE BRANDWAYN Unsplash

Flynn’s Taxonomy and the Concept of Multithreading

Scientific American Supplement, No. 392, July 7, 1883 by Various, is part of the HackerNoon Books Series. You can jump to any chapter in this book . ST. BLAISE, THE WINNER OF THE DERBY. here ST. BLAISE, THE WINNER OF THE DERBY. St. Blaise, the property of Sir Frederick Johnstone, was bred by Lord Alington, and is by Hermit from Fusee. This is an unexceptionable pedigree, for Hermit is now as successful and fashionable a sire as was even Stockwell in his palmiest days, while Fusee was far more than an average performer on the turf, and won several Queen's Plates and other races over a distance of ground. St. Blaise is by no means a big colt, standing considerably under sixteen hands. His color is about his worst point, as he is a light, washy chestnut, with a bald face and three white heels. He has a good head and neck, and very powerful back and muscular quarters, added to which his legs and feet are well shaped and thoroughly sound. His first appearance was made in the Twenty-fourth Stockbridge Biennial at the Bibury Club Meeting, when he won easily enough; but there were only four moderate animals behind him. A walk-over for the Troy Stakes followed, and then Macheath beat him easily enough for the Hurstbourne Stakes, though he finished in front of Adriana and Tyndrum. For the Molecomb Stakes at Goodwood, he ran a dead-heat with Elzevir, to whom he was giving 7 lb.; and Bonny Jean, in receipt of 10 lb., was unplaced. A 7 lb. penalty seemed to put him completely out of the Dewhurst Plate; but he must then have been out of form, as, on the following day, it took him all his time to defeat Pebble by a neck in the Troy Stakes. This season he has only run twice. His fourth in the Two Thousand was by no means a bad performance, considering that he was palpably backward; and his victory of last week is too recent to need further allusion. Porter, his trainer, can boast of several other successes in the great race at Epsom; but Charles Wood had never previously ridden a Derby winner. St. Blaise was unfortunately omitted from the entries for the St. Leger, but has several valuable engagements at Ascot next week, and appears to have the Grand Prize of Paris, on Sunday, at his mercy.-- . Illustrated London News [NATURE.] SCIENTIFIC PROGRESS IN CHINA AND JAPAN. Various steps in the progress of China, and Japan in the adoption of Western science and educational methods have from time to time been noticed in these columns. To the popular mind the names of the two countries are synonymous with rigid, unreasoning conservatism and with rapid change, respectively. The grave, dignified Chinese, who maintains his own dress and habits even when isolated among strangers, and whose motto appears to be, , is popularly believed to be animated by a sullen, obstinate hostility toward any introduction from the West, however plain its value may be; while his gayer and more mercurial neighbor, the Japanese, is regarded as the true child of the old age of the West, following assiduously in its parent's footsteps, and pursuing obediently the path marked out by European experience. There is considerable misconception in this, as indeed there is at all times in the English popular mind with regard to strange peoples. Broadly speaking, it is no doubt correct to say that, Japan has adopted Western inventions and scientific appliances with avidity; that she has shown a desire for change which is abnormal, and a disposition to destroy her charts and sail away into unsurveyed seas, while China remains pretty much where she always was. She is now, with some exceptions, what she was twenty, two hundred, perhaps two thousand years ago, while a new Japan has been created in fifteen years. All this, we say, is true, but it is not the whole truth. China also has had her changes; not indeed so marked or rapid, not so much in the nature of a on all her past as those of her neighbor. Stare super mas antiquas volte-face The radical difference between the two countries in this respect we take to be this: that while Japan loves change for the sake of change, China dislikes it, and will only adopt it when it is clearly demonstrated to her that change is absolutely necessary. To the Japanese change appears to be a delightful excitement, to the Chinese a distasteful necessity; to the former whatever is must be wrong, to the latter whatever is is right. As a consequence of this difference between the two peoples, when China once makes a step forward it is generally after much deliberation, and is never retraced. Japan is constantly undertaking new schemes with little care or thought for the morrow, but with the applause of injudicious foreign friends. In a short time she discovers that she has underrated the expense or exaggerated the results, and her projects are straightway abandoned as rapidly and thoughtlessly as they were commenced. Swift suggested as a suitable subject for a philosophical writer a history of human projects which were never carried out; the historian of modern Japan finds these at every turn. Where, for example, are the results of the great surveys, trigonometrical and others, which were commenced in Yezo and the main island about ten years ago? A large, expensive, but highly competent foreign staff was engaged, and worked for a few years; but suddenly the whole survey department was swept away, and the valuable instruments are, or were recently, lying rusting in a warehouse in Tokio. The same story may be told of scores of other scientific or educational undertakings in Japan. An able and careful writer, Col. H.S. Palmer, R.E., who has recently, with a friendly and sympathetic eye, examined the whole field of recent Japanese progress, in the is forced to acknowledge this. "Once having recognized," says this officer, "that progress is essential to welfare, and having resolved, first among the nations of the East, to throw off past traditions and mould their civilization after that of Western countries, it was not in the nature of the lively and impulsive Japanese to advance along the path of reform with the calmness and circumspection that might have been possible to a people of less active temperament. Without doubt many foreign institutions were at first adopted rather too hastily, and the passing difficulties which now beset Japan are to some extent the inevitable result." It would be blindness to deny that the net result of the Japanese efforts is progress of a very remarkable kind, but it is a progress which in many respects lacks the firm and abiding characteristics of Chinese movements. British Quarterly Review The proverb, , which was recommended ten years ago to Japanese attention by an eminent English official, and apparently disregarded by them, has been adopted by their continental neighbors. To the blandishments of pushing diplomatists or acute promoters, the Chinese are deaf. However we may felicitate ourselves on our inventions, scientific appliances, "the railway and the steamship and the thoughts that shake mankind," our progress, the newspapers, the penny post, and what not, China will not adopt them simply because have found their value and are proud of them. But if, within the range of her own experience, she finds the advantage of these things, she will employ them with a rapidity and decision surpassing those of the Japanese. A conspicuous instance of this will be found in her recent action with respect to telegraphs. For years the Chinese steadily refused to have anything to do with them; the small land line which connected the foreign community of Shanghai with the outer world, was maintained against the violent protests of the local authorities, and the cable companies experienced some difficulty in getting permission to land their cables. But during the winter of 1870-80, when war with Russia was threatened, the value of telegraphs was demonstrated to the Peking government. The Peiho at Tientsin was closed by ice against steamers, and news could only be carried to the capital by overland couriers from Shanghai. Before a year elapsed a land line of telegraph was being constructed between this port and Tientsin; in a few months the line was in working order, and the Chinese metropolis is now in telegraphic communication with every capital in Europe. Chi va piano va sano we This conservatism, respect for antiquity, conceit, prejudice, call it what we will, has something in it that extorts our respect. Let us imagine a dignified and cultivated Chinese official conversing with a pushing Manchester or Birmingham manufacturer, who descants on the benefits of our modern inventions. He would probably commune with himself in this wise, whatever reply Oriental politeness would dictate to his interviewer: "China has got on very well for some tens of centuries without the curious things of which this foreigner speaks; she has produced in this time statesmen, poets, philosophers, soldiers; her people appear to have had their share of affliction, but not more than those of Europe; why should we now turn round at the bidding of a handful of strangers who know little of us or our country, and make violent changes in our life and habits? A railway in a province will throw thousands of coolies and boatmen out of employment and bring on them misery and starvation. This foreigner says that railways and telegraphs have been found beneficial in his country; good, let his countrymen have them if they please, but let us rest as we are for the present. Moreover, past events have not given us such faith in Europeans that we should take all they say for wisdom and justice." A day will undoubtedly come when China also will have her great mechanical and scientific enterprises; but what we contend for here is that nothing we can say or do will bring that time an hour nearer. European public opinion is to China a dead letter; she refuses to plead before that tribunal. Each step of her advance along our path must be the result of her own reflection and experience; and our wisest policy would be to leave her to herself to advance on it as she deems best. SINENSIS. About HackerNoon Book Series: We bring you the most important technical, scientific, and insightful public domain books. This book is part of the public domain. Various (2005). Scientific American Supplement, No. 392, July 7, 1883. Urbana, Illinois: Project Gutenberg. Retrieved https://www.gutenberg.org/cache/epub/8742/pg8742-images.html This eBook is for the use of anyone anywhere at no cost and with almost no restrictions whatsoever. You may copy it, give it away or re-use it under the terms of the Project Gutenberg License included with this eBook or online at , located at . www.gutenberg.org https://www.gutenberg.org/policy/license.html

ST. BLAISE, THE WINNER OF THE DERBY

The Murder on the Links by Agatha Christie, is part of the HackerNoon Books Series. You can jump to any chapter in this book here . An Amazing Statement XX. An Amazing Statement The next moment Poirot embraced me warmly. “Enfin! You have arrived. And all by yourself. It is superb! Continue your reasoning. You are right. Decidedly we have done wrong to forget Georges Conneau.” I was so flattered by the little man’s approval that I could hardly continue. But at last I collected my thoughts and went on. “Georges Conneau disappeared twenty years ago, but we have no reason to believe that he is dead.” “Aucunement,” agreed Poirot. “Proceed.” “Therefore we will assume that he is alive.” “Exactly.” “Or that he was alive until recently.” “De mieux en mieux!” “We will presume,” I continued, my enthusiasm rising, “that he has fallen on evil days. He has become a criminal, an apache, a tramp—a what you will. He chances to come to Merlinville. There he finds the woman he has never ceased to love.” “Eh eh! The sentimentality,” warned Poirot. “Where one hates one also loves,” I quoted or misquoted. “At any rate he finds her there, living under an assumed name. But she has a new lover, the Englishman, Renauld. Georges Conneau, the memory of old wrongs rising in him, quarrels with this Renauld. He lies in wait for him as he comes to visit his mistress, and stabs him in the back. Then, terrified at what he has done, he starts to dig a grave. I imagine it likely that Madame Daubreuil comes out to look for her lover. She and Conneau have a terrible scene. He drags her into the shed, and there suddenly falls down in an epileptic fit. Now supposing Jack Renauld to appear. Madame Daubreuil tells him all, points out to him the dreadful consequences to her daughter if this scandal of the past is revived. His father’s murderer is dead—let them do their best to hush it up. Jack Renauld consents—goes to the house and has an interview with his mother, winning her over to his point of view. Primed with the story that Madame Daubreuil has suggested to him, she permits herself to be gagged and bound. There, Poirot, what do you think of that?” I leaned back, flushed with the pride of successful reconstruction. Poirot looked at me thoughtfully. “I think that you should write for the Kinema, mon ami,” he remarked at last. “You mean—?” “It would make a good film, the story that you have recounted to me there—but it bears no sort of resemblance to everyday life.” “I admit that I haven’t gone into all the details, but—” “You have gone further—you have ignored them magnificently. What about the way the two men were dressed? Do you suggest that after stabbing his victim, Conneau removed his suit of clothes, donned it himself, and replaced the dagger?” “I don’t see that that matters,” I objected rather huffily. “He may have obtained clothes and money from Madame Daubreuil by threats earlier in the day.” “By threats—eh? You seriously advance that supposition?” “Certainly. He could have threatened to reveal her identity to the Renaulds, which would probably have put an end to all hopes of her daughter’s marriage.” “You are wrong, Hastings. He could not blackmail her, for she had the whip hand. Georges Conneau, remember, is still wanted for murder. A word from her and he is in danger of the guillotine.” I was forced, rather reluctantly, to admit the truth of this. “Your theory,” I remarked acidly, “is doubtless correct as to all the details?” “My theory is the truth,” said Poirot quietly. “And the truth is necessarily correct. In your theory you made a fundamental error. You permitted your imagination to lead you astray with midnight assignations and passionate love scenes. But in investigating crime we must take our stand upon the commonplace. Shall I demonstrate my methods to you?” “Oh, by all means let us have a demonstration!” Poirot sat very upright and began, wagging his forefinger emphatically to emphasize his points. “I will start as you started from the basic fact of Georges Conneau. Now the story told by Madame Beroldy in court as to the ‘Russians’ was admittedly a fabrication. If she was innocent of connivance in the crime, it was concocted by her, and by her only as she stated. If, on the other hand, she was not innocent, it might have been invented by either her or Georges Conneau. “Now in this case we are investigating, we meet the same tale. As I pointed out to you, the facts render it very unlikely that Madame Daubreuil inspired it. So we turn to the hypothesis that the story had its origin in the brain of Georges Conneau. Very good. Georges Conneau, therefore, planned the crime with Madame Renauld as his accomplice. She is in the limelight, and behind her is a shadowy figure whose alias is unknown to us. “Now let us go carefully over the Renauld Case from the beginning, setting down each significant point in its chronological order. You have a notebook and pencil? Good. Now what is the earliest point to note down?” “The letter to you?” “That was the first we knew of it, but it is not the proper beginning of the case. The first point of any significance, I should say, is the change that came over M. Renauld shortly after arriving in Merlinville, and which is attested to by several witnesses. We have also to consider his friendship with Madame Daubreuil, and the large sums of money paid over to her. From thence we can come directly to the 23rd May.” Poirot paused, cleared his throat, and signed to me to write. “23rd May. M. Renauld quarrels with his son over latter’s wish to marry Marthe Daubreuil. Son leaves for Paris. “24th May. M. Renauld alters his will, leaving entire control of his fortune in his wife’s hands. “7th June. Quarrel with tramp in garden, witnessed by Marthe Daubreuil. “Letter written to M. Hercule Poirot, imploring assistance. “Telegram sent to Jack Renauld, bidding him proceed by the Anzora to Buenos Ayres. “Chauffeur, Masters, sent off on a holiday. “Visit of a lady, that evening. As he is seeing her out, his words are ‘Yes, yes—but for God’s sake go now. …’ ” Poirot paused. “There, Hastings, take each of those facts one by one, consider them carefully by themselves and in relation to the whole, and see if you do not get new light on the matter.” I endeavoured conscientiously to do as he had said. After a moment or two, I said rather doubtfully: “As to the first points, the question seems to be whether we adopt the theory of blackmail, or of an infatuation for this woman.” “Blackmail, decidedly. You heard what Stonor said as to his character and habits.” “Mrs. Renauld did not confirm his view,” I argued. “We have already seen that Madame Renauld’s testimony cannot be relied upon in any way. We must trust to Stonor on that point.” “Still, if Renauld had an affair with a woman called Bella, there seems no inherent improbability in his having another with Madame Daubreuil.” “None whatever, I grant you, Hastings. But did he?” “The letter, Poirot. You forget the letter.” “No, I do not forget. But what makes you think that letter was written to M. Renauld?” “Why it was found in his pocket and—and—” “And that is all!” cut in Poirot. “There was no mention of any name to show to whom the letter was addressed. We assumed it was to the dead man because it was in the pocket of his overcoat. Now, mon ami, something about that overcoat struck me as unusual. I measured it, and made the remark that he wore his overcoat very long. That remark should have given you to think.” “I thought you were just saying it for the sake of saying something,” I confessed. “Ah, quelle idée! Later you observed me measuring the overcoat of M. Jack Renauld. Eh bien, M. Jack Renauld wears his overcoat very short. Put those two facts together with a third, namely that M. Jack Renauld flung out of the house in a hurry on his departure for Paris, and tell me what you make of it!” “I see,” I said slowly, as the meaning of Poirot’s remarks bore in upon me. “That letter was written to Jack Renauld—not to his father. He caught up the wrong overcoat in his haste and agitation.” Poirot nodded. “Précisement! We can return to this point later. For the moment let us content ourselves with accepting the letter as having nothing to do with M. Renauld père, and pass to the next chronological event.” “May 23rd,” I read, “M. Renauld quarrels with his son over latter’s wish to marry Marthe Daubreuil. Son leaves for Paris. I don’t see anything much to remark upon there, and the altering of the will the following day seems straightforward enough. It was the direct result of the quarrel.” “We agree, mon ami—at least as to the cause. But what exact motive underlay this procedure of M. Renauld’s?” I opened my eyes in surprise. “Anger against his son of course.” “Yet he wrote him affectionate letters to Paris?” “So Jack Renauld says, but he cannot produce them.” “Well, let us pass from that.” “Now we come to the day of the tragedy. You have placed the events of the morning in a certain order. Have you any justification for that?” “I have ascertained that the letter to me was posted at the same time as the telegram was despatched. Masters was informed he could take a holiday shortly afterwards. In my opinion the quarrel with the tramp took place anterior to these happenings.” “I do not see that you can fix that definitely—unless you question Mademoiselle Dabreuil again.” “There is no need. I am sure of it. And if you do not see that, you see nothing, Hastings!” I looked at him for a moment. “Of course! I am an idiot. If the tramp was Georges Conneau, it was after the stormy interview with him that Mr. Renauld apprehended danger. He sent away the chauffeur, Masters, whom he suspected of being in the other’s pay, he wired to his son, and sent for you.” A faint smile crossed Poirot’s lips. “You do not think it strange that he should use exactly the same expressions in his letter as Madame Renauld used later in her story? If the mention of Santiago was a blind, why should Renauld speak of it, and—what is more—send his son there?” “It is puzzling, I admit, but perhaps we shall find some explanation later. We come now to the evening, and the visit of the mysterious lady. I confess that that fairly baffles me, unless it was Madame Daubreuil, as Françoise all along maintained.” Poirot shook his head. “My friend, my friend, where are your wits wandering? Remember the fragment of cheque, and the fact that the name Bella Duveen was faintly familiar to Stonor, and I think we may take it for granted that Bella Duveen is the full name of Jack’s unknown correspondent, and that it was she who came to the Villa Geneviève that night. Whether she intended to see Jack, or whether she meant all along to appeal to his father we cannot be certain, but I think we may assume that this is what occurred. She produced her claim upon Jack, probably showed letters that he had written her, and the older man tried to buy her off by writing a cheque. This she indignantly tore up. The terms of her letter are those of a woman genuinely in love, and she would probably deeply resent being offered money. In the end he got rid of her, and here the words that he used are significant.” “ ‘Yes, yes, but for God’s sake go now,’ ” I repeated. “They seem to me a little vehement, perhaps, that is all.” “That is enough. He was desperately anxious for the girl to go. Why? Not only because the interview was unpleasant. No, it was the time that was slipping by, and for some reason time was precious.” “Why should it be?” I asked, bewildered. “That is what we ask ourselves. Why should it be? But later we have the incident of the wrist watch—which again shows us that time plays a very important part in the crime. We are now fast approaching the actual drama. It is half-past ten when Bella Duveen leaves, and by the evidence of the wrist watch we know that the crime was committed, or at any rate that it was staged, before twelve o’clock. We have reviewed all the events anterior to the murder, there remains only one unplaced. By the doctor’s evidence, the tramp, when found, had been dead at least forty-eight hours—with a possible margin of twenty-four hours more. Now, with no other facts to help me than those we have discussed, I place the death as having occurred on the morning of June 7th.” I stared at him, stupefied. “But how? Why? How can you possibly know?” “Because only in that way can the sequence of events be logically explained. Mon ami, I have taken you step by step along the way. Do you not now see what is so glaringly plain?” “My dear Poirot, I can’t see anything glaring about it. I did think I was beginning to see my way before, but I’m now hopelessly fogged.” Poirot looked at me sadly, and shook his head. “Mon Dieu! But it is triste! A good intelligence—and so deplorably lacking in method. There is an exercise most excellent for the development of the little grey cells. I will impart it to you—” “For Heaven’s sake, not now! You really are the most irritating of fellows, Poirot. For goodness’ sake, get on and tell me who killed M. Renauld.” “That is just what I am not sure of as yet.” “But you said it was glaringly clear?” “We talk at cross-purposes, my friend. Remember, it is two crimes we are investigating—for which, as I pointed out to you, we have the necessary two bodies. There, there, ne vous impatientez pas! I explain all. To begin with, we apply our psychology. We find three points at which M. Renauld displays a distinct change of view and action—three psychological points therefore. The first occurs immediately after arriving in Merlinville, the second after quarrelling with his son on a certain subject, the third on the morning of June 7th. Now for the three causes. We can attribute No. 1 to meeting Madame Daubreuil. No. 2 is indirectly connected with her since it concerns a marriage between M. Renauld’s son and her daughter. But the cause of No. 3 is hidden from us. We have to deduce it. Now, mon ami, let me ask you a question; who do we believe to have planned this crime?” “Georges Conneau,” I said doubtfully, eyeing Poirot warily. “Exactly. Now Giraud laid it down as an axiom that a woman lies to save herself, the man she loves, and her child. Since we are satisfied that was Georges Conneau who dictated the lie to her, and as Georges Conneau is not Jack Renauld, follows that the third case is put out of court. And, still attributing the crime to Georges Conneau, the first is equally so. So we are forced to the second—that Madame Renauld lied for the sake of the man she loved—or in other words, for the sake of Georges Conneau. You agree to that.” “Yes,” I admitted. “It seems logical enough.” “Bien! Madame Renauld loves Georges Conneau. Who, then, is Georges Conneau?” “The tramp.” “Have we any evidence to show that Madame Renauld loved the tramp?” “No, but—” “Very well then. Do not cling to theories where facts no longer support them. Ask yourself instead who Madame Renauld did love.” I shook my head perplexed. “Mais, oui, you know perfectly. Who did Madame Renauld love so dearly that when she saw his dead body, she fell down in a swoon?” I stared dumbfounded. “Her husband?” I gasped. Poirot nodded. “Her husband—or Georges Conneau, whichever you like to call him.” I rallied myself. “But it’s impossible.” “How ‘impossible?’ Did we not agree just now that Madame Daubreuil was in a position to blackmail Georges Conneau?” “Yes, but—” “And did she not very effectively blackmail M. Renauld?” “That may be true enough, but—” “And is it not a fact that we know nothing of M. Renauld’s youth and upbringing? That he springs suddenly into existence as a French Canadian exactly twenty-two years ago?” “All that is so,” I said more firmly, “but you seem to me to be overlooking one salient point.” “What is it, my friend?” “Why, we have admitted Georges Conneau planned the crime. That brings us to the ridiculous statement that he planned his own murder!” “Eh bien, mon ami,” said Poirot placidly, “that is just what he did do!” About HackerNoon Book Series: We bring you the most important technical, scientific, and insightful public domain books. This book is part of the public domain. Agatha Christie (2019). The Murder on the Links. Urbana, Illinois: Project Gutenberg. Retrieved https://www.gutenberg.org/cache/epub/58866/pg58866-images.html This eBook is for the use of anyone anywhere at no cost and with almost no restrictions whatsoever. You may copy it, give it away or re-use it under the terms of the Project Gutenberg License included with this eBook or online at www.gutenberg.org , located at https://www.gutenberg.org/policy/license.html.

An Amazing Statement

Hi guys, I want to introduce . It's a React.js for . With it you can build your own places autocomplete UI like the following demo easily! Hope you guys 👍🏻 it. use-places-autocomplete hook Google Maps Places Autocomplete ⚡️ Try yourself: https://use-places-autocomplete.netlify.app Features 🧠 Provides intelligent places suggestions powered by . Google Maps Places API 🎣 Builds your own customized autocomplete UI by React . hook 🔧 to do geocoding and get geographic coordinates using . Utility functions Google Maps Geocoding API 🤑 Built-in for you to save the cost of Google APIs. cache mechanism 💰 Built-in debounce mechanism for you to lower the cost of Google APIs. 🚀 Supports asynchronous Google script loading. 📜 Supports type definition. TypeScript ⌨️ Builds a UX-rich component (e.g. and keyword support) via comprehensive . WAI-ARIA compliant demo code 🦔 Tiny size ( ). No external dependencies, aside for the . ~ 1.7KB gzipped react How does it work? First, use the script tag to load the library in your project. <script src= "https://maps.googleapis.com/maps/api/js?key=YOUR_API_KEY&libraries=places" ></script> Start to build our component. Check the out to learn more. API getGeocode,
  getLatLng, ready,
    value, setValue,
    clearSuggestions,
  } = usePlacesAutocomplete({ }, }); clearSuggestions();
  }); setValue(e.target.value);
  }; clearSuggestions(); });
    }; place_id, } = suggestion; );
    }); );
}; import usePlacesAutocomplete, { } from "use-places-autocomplete" ; import useOnclickOutside from "react-cool-onclickoutside" ; const PlacesAutocomplete = () => { const { suggestions : { status, data }, requestOptions : { /* Define search scope here */ debounce : 300 , const ref = useOnclickOutside( () => { // When user clicks outside of the component, we can dismiss // the searched suggestions by calling this method const handleInput = ( e ) => { // Update the keyword of the input element const handleSelect = ( { description } ) => () => { // When user selects a place, we can replace the keyword without request data from API // by setting the second parameter to "false" setValue(description, false ); // Get latitude and longitude via utility functions getGeocode({ address : description }).then( ( results ) => { const { lat, lng } = getLatLng(results[ 0 ]); console .log( "📍 Coordinates: " , { lat, lng }); const renderSuggestions = () => data.map( ( suggestion ) => { const { structured_formatting : { main_text, secondary_text }, return ( < li key = {place_id} onClick = {handleSelect(suggestion)} > < strong > {main_text} </ strong > < small > {secondary_text} </ small > </ li > return ( < div ref = {ref} > < input value = {value} onChange = {handleInput} disabled = {!ready} placeholder = "Where are you going?" /> {/* We can use the "status" to decide whether we should display the dropdown or not */} {status === "OK" && < ul > {renderSuggestions()} </ ul > } </ div > Easy right? This is the magic of the ✨. I just show you how does it work via the minimal example. However there're more things you can do for an UX rich autocomplete component, like and keyword support as my (check the ), a keyword clear button, search history etc. usePlacesAutocomplete WAI-ARIA compliant demo code 💡 is my other hook library, which can help you handle the interaction of user clicks outside of the component(s). react-cool-onclickoutside Thanks for reading, for more usage details checkout the project's GitHub page: https://github.com/wellyshen/use-places-autocomplete You can also install this package is distributed via . npm $ npm install --save use-places-autocomplete $ yarn add use-places-autocomplete # or When working with TypeScript you need to install the as a . @types/googlemaps devDependencies $ yarn add --dev @types /googlemaps # or $ npm install --save-dev @types /googlemaps

Create your React.js Address Autocomplete Component in 10 minutes ⏰

In our , we introduced sequential consistency, the threading programming contract between programmers and computer systems. last installment We are about to dive further into the most common memory consistency model in practice, . The beauty of this consistency is that while it's much cheaper for systems to implement, given proper locking however, we can formally prove that it is equivalent to sequential consistency. release consistency After finishing this article, C++'s documentation will actually look like English to you. You will also feel more at ease navigating the water crafting your own synchronization methods, without resorting to off-the-shelf solutions such as library-provided locks. std::memory_order But first, it's necessary to make a detour to get acquainted with the staple of multi-thread programming: locks, which is so essential to 's intuition and implementation. release consistency Locks Use case In our last episode, we covered an example in which two threads race to update two variables and . Let's reuse it as our in this article: i j example1 i = ; j = ; output[ ]; {
  i = ;
  output[ ] = j;
} {
  j = ;
  output[ ] = i;
} int 0 int 0 int 2 void func0 () 1 1 void func1 () 1 0 Honestly, this was only a contrived example perfectly fit for demonstrating broken memory consistencies. The most common synchronization need actually arises from the necessity of grouping multiple memory operations in one shot. This need was as old as the concept of multithreading. It even predates SMP or consistency model. Let's look at a more realistic . example2 id = ; my_id[ ]; { my_id[ ] = id++; } { my_id[ ] = id++; } int 0 int 2 void func0 () 0 void func1 () 1 Here we have two threads wanting to generate their own unique IDs. The hazard here is that the innocent increment is actually two memory operations slammed together. It's commonly referred to as . If we paste this snippet into , we can show that on x86 each function roughly takes 4 instructions -- read-add-write for and the assigning the value to : id++ read-modify-write compiler explorer id++ my_id func0():                              # @func0()
        movl    id(%rip), %eax
        leal (%rax), %ecx
        movl    %ecx, id(%rip)
        movl    %eax, my_id(%rip)
        retq 1 Of course, we're not counting the function return as a proper instruction here. The race condition is evident. If both threads will do the reads first before the other completes the whole read-modify-write sequence, it'll be possible for both threads to get an ID of 0. We can also write a full program that produces this result: id = ; my_id[ ]; { my_id[ ] = id++; } { my_id[ ] = id++; } {
  id = ; :: ; :: ;

  t0.join();
  t1.join(); :: << my_id[ ] << my_id[ ] << :: ;
} { (;;) {
    run_test();
  } ;
} # include <iostream> # include <thread> int 0 int 2 void func0 () 0 void func1 () 1 void run_test () 0 std thread t0 (func0) std thread t1 (func1) std cout 0 1 std endl int main () for return 0 Do you see that we're fundamentally dealing with a different issue that here? can break because instructions can be reordered, and here we break because instructions may be interleaved, even when they are completely executed in program order! example1 Example 1 One way to solve the problem is to wrap in an construct and convert the increment to its API, which just generates a special hardware atomic instruction that takes care of the read-modify-write business. But that's just a shortcut. Prior to the C++11 standard, we would have just put the read-modify-write sequence of in a good old critical section, protected by locks, so that the access to it will be mutually excluded. id std::atomic fetch_add id Spinlock implementation How are locks implemented though? It turns out, the locking is just a read-modify-write on its own. Let's take a look at the most simple kind of lock -- spinlock. Here we can have a simplistic working implementation using C++'s . In the old days, we would have embedded assembly ourselves. std::atomic : { (;;) { expected_val = ; (busy.compare_exchange_strong(expected_val, )) ;
    }
  } { busy.store( ); } : ::atomic< > busy = ;
}; { class spinlock public void lock () for bool false if true return void unlock () false private std bool false It's called spinlock because the acquisition keeps spinning on the lock state hoping it won't be busy the next moment without ever blocking. A spinlock state could be as little as 1 bit. shows that acquiring the lock generates a (standing for compare-and-exchange) instruction: Compiler explorer cmpxchg main:                                   # @main
        movb    $ , (%rsp)
        movb    $ , %cl
.LBB0_1:                                # =>This Inner Loop Header: Depth= xorl    %eax, %eax
        lock            cmpxchgb        %cl, (%rsp)
        jne     .LBB0_1
        movb    $ , (%rsp)
        xorl    %eax, %eax
        retq 0 -8 1 1 -8 0 -8 This instruction does the following: 1) it reads out the lock state, 2) compares to the expected "not busy" value, and 3) if equal, writes the "busy" value back to the lock state. The operation can succeed or fail, and if it fails we'll just keep retrying till we actually acquire the lock. But either way, the 3 things are done together without interruption. Again, read, update, and write: The lock release doesn't have to be retried, and we unconditionally write a "not busy" value to the lock state. Note here you can pretend we have sequential consistency here. For now, you will have to trust me that the lock code will work in both uniprocessor and multiprocessor environments. After finishing the article you will see why. Now let's protect the variable using our spinlock, and both our IDs should be unique. id #include <atomic>
#include <iostream>
#include <mutex>
#include <thread> {
public: lock() { (;;) {
      bool expected_val = ; (busy.compare_exchange_strong(expected_val, )) ;
    }
  } unlock() { busy.store( ); }

private:
  std::atomic<bool> busy = ;
};

spinlock m;
int id = ;
int my_id[ ]; func0() { ::lock_guard g(m);
  my_id[ ] = id++;
} func1() { ::lock_guard g(m);
  my_id[ ] = id++;
} run_test() {
  id = ;

  std::thread t0(func0);
  std::thread t1(func1);

  t0.join();
  t1.join();
  std::cout << my_id[ ] << my_id[ ] << std::endl;
}

int main() { (;;) {
    run_test();
  } ;
} class spinlock void for false if true return void false false 0 2 void std 0 void std 1 void 0 0 1 for return 0 Release consistency Finally, we have got around to the main course of this episode. Recall that sequential consistency, for the most part, requires that there's a global ordering of all memory operations. This is very hard to implement on modern processors. X is one attempt at relaxing the memory access orders, and we could see in the last episode that it will break sequential consistency if accesses to shared variables aren't properly ordered. 86 TSO People have noticed that more often than not, shared variables ARE actually protected by locks. Like we mentioned before, this habit predates multiprocessors, so it has nothing to do with coping with memory reordering. But since locks are such special memory locations, it's tempting the think that instead of enforcing memory orders everywhere, maybe we can do something clever to the locks to maintain the sequential consistency illusion, while letting the general population of the instructions slide? This is where (RC) comes in. There are two flavors of RC, RCsc and RCpc. Both are equivalent. Let's start with RCsc, which is easier to understand, but less practical to implement compared to RCpc. release consistency RCsc These points summarize RCsc: Memory accesses are categorized into a) , acquiring and releasing a lock, and b) . synchronization ops i.e. ordinary ops No local memory accesses can be reordered after a release op. No local memory accesses can be reordered before an acquire op. Synchronization ops themselves observe sequential consistency, hence the "sc" subscript in the consistency name. This is where I want to put in a thousand words to describe the mechanism. So let's throw in a picture instead. This illustrates why these points will maintain the sequential consistency illusion. Imagine we have two critical sections (CS) executing on two processors A and B, referred to as and respectively. These are shown as two boxes in the diagram above. The critical sections are protected by a single lock. Inside the CS'es there are some accesses to locations private to the processors themselves, and some accesses to shared variables. It's easy to prove that all accesses in will strictly happen before all accesses in , and this is observed globally. The most important trick is the sequential consistency ordering between the and the established in rule No. 4. That is, CS-A CS-B CS-A CS-B CS-A release CS-B acquire CS-A release < CS-B acquire where the "<" sign denotes the global happens-before relationship. From rule No. 2 and 3, any op in will finish before the . Also any op in will finish after the . So we have the following: CS-A CS-A release CS-B CS-B acquire , and Op in CS-A < CS-A release CS-B acquire < Op in CS-B Finally, transitively, any op in will globally happen before any op in . CS-A CS-B The private accesses are irrelevant here, because at any time they are done by a single processor, and the global order is defined by that processor's order, which is guaranteed to be equivalent to sequential consistency, even though some reordering might happen. Also our strong happens-before relationship have put the shared accesses into the same situation. At any time there's only one processor doing the accesses exclusively, so the order it executes will be defined as the global order. This order must be equivalent to a sequential consistency order, which is the golden rule no system dares to break so far. You can see that all is banking on, is that outside the critical sections there shouldn't be any shared access. If you do, you're on your own for defining the access ordering. This is why C++11 kind of accesses unprotected by locks or and related constructs. Going back to at the very beginning, as alternatives to using , we could potentially use a proper lock to achieve the same purpose. release consistency outlawed std::atomic example1 std::atomic RCpc We just proved that as long as data are always protected by locks, RCsc will be equivalent to sequential consistency. However, ruminating over the requirements RCsc here, you might find it very hard to implement on actual processors. It asks for 2 kinds of ordering enforcement: sequential consistency between sync ops, and a local ordering between sync and ordinary ops. Think about how you would provide that interface when you design instructions. Common architectures just give you local memory fences. For example, has a MFENCE instruction that prevents local memory operations from being ordered across that instruction. x86 Now RCpc comes along and stops us from worrying. It says sequential consistency between sync ops might be more than sufficient. We can replace it with a consistency model called , and the world will keep revolving. processor consistency assumes that each processor has its own local memory (which is a very realistic assumption, since commonly "cores" have their own private L1 cache). Processor consistency I have deliberately refrained from linking a Wikipedia definition of here. If you must look, I'd have to caution you that this is one of the rare cases Wikipedia is wrong! Look at one of its figures: processor consistency This is an example given to explain . What this says is issues a write of value to location . receives that value, and writes to the same location . observe the two writes in different orders. This is definitely not true for processor consistency, because cache coherency protocols would have prevented that. This article is getting long, so maybe we will go through cache coherency when we look at some locking performance issues. For now, this sums up the concepts very nicely. Hypothetically some of you might have extra time for some extensive reading. processor consistency Processor1 1 x Processor2 2 x Processor3 and processor4 survey paper Essentially, is only concerned about memory ordering w.r.t. a single memory location. Suppose we have a single lock, for that lock can be thought of as a series of writes to the lock, and these writes are globally ordered. Reads from different threads however, may observe them at different timings. processor consistency processor consistency To illustrate why won't be an issue in the context of release consistency, let's look at the figure above and consider a theoretical case where 3 processors, yellow, purple and green are executing a few operations. At first yellow grabs the lock using a compare-and-exchange instruction, which is 3 ops executed without interruption. Shortly, it releases the lock. processor consistency The write operations (acquire and release) are propagated to purple first. On seeing the lock released, purple seized the opportunity and acquired the lock for its own use. Meanwhile, green only sees a release from yellow, and it tries its 3-op sequence to acquire the lock too, but dictates that the acquire op has to be a failure, because it is a write op, and it has to fit into the global ordering. So no harm is done -- green can just retry in the future without jeopardizing the lock semantics. processor consistency In reality, cache coherency protocols usually makes one processor exclusively execute the read-modify-write on the lock cache line at a time. So realistically the chart will look more like this: You might think this looks awfully like , but it's not. We are only dealing with one memory location here (the lock), whereas mandates a total operation ordering, across all memory locations. sequential consistency sequential consistency In the cases where you need to acquiring multiple locks to get to the critical section, this model will guarantee correctness as well. The proof is assigned to you, the reader, as an exercise. 😀 This is great news! So as long as a processor implements as its memory consistency by default, we can safely build on top to present programmers sequential consistency, provided all shared memory accesses are protected by locks. In reality is a very reasonable thing to assume, given how cache coherency is implemented. More on that topic later. processor consistency processor consistency It might be obvious but let's spend a few words on building on top of to implement . Given the RCpc requirement, with the native , the only thing missing is the local ordering between acquire/release and ordinary memory operations. processor consistency release consistency processor consistency Like we said, usually the instruction set architecture will give you some control as to inserting barrier or fence instructions to enforce some kind of local ordering. has three of them, LFENCE, SFENCE and MFENCE. But only MFENCE is actually of any use to us. for example, has DMB and DSB instructions that function similarly. Now we're good to go! X86 ARM Even though there are a myriad of consistency models, is the weakest of them all that works. That's why you can ignore all other consistency models such as and so on. And even isn't all that interesting to understand either, aside from the fact that it's the consistency model of THE x86. release consistency causal, weak ordering, PowerPC x86 TSO Coda: Revisit our spinlock implementation Now that you have understood how works, you can probably see that our spinlock implementation at the beginning can be somehow improved in that the atomic accesses to the lock state don't have to be . release consistency sequential consistency There are other spinlock implementations from established orgs. The simplest is Facebook's . Our simplest example is just a tiny bit different from it, in that: folly Folly tries to avoid when possible. sequential consistency If a spinlock acquire operation fails, it executes the PAUSE x86 instruction to wait for a tiny bit. This tells the processor to kill all speculative executions to make space for other hyperthreads on the same core. We can definitely incorporate the memory order weakening part into our implementation easily: {
public: lock() { (;;) {
      bool expected_val = ; (busy.compare_exchange_strong(expected_val, , ::memory_order_acquire, ::memory_order_relaxed)) ;
    }
  } unlock() { busy.store( , ::memory_order_release); }

private:
  std::atomic<bool> busy = ;
}; class spinlock void for false if true std std return void false std false Now there's a funny thing. I won't paste it here, but if you watch the binaries from these two versions, you won't observe a tiny bit of difference. Why? ? At the very least would you think you should see some memory fence instructions removed in the new implementation The reason is the instruction itself brings an implicit memory barrier. So a call on x86 with weakened memory ordering isn't all that meaningful, because the architecture doesn't give the compiler an option. cmpxchg compare_exchange As to the release, remember only brings loads forward, bypassing stores to different locations? There's never a time it will reorder instructions backwards, so the "release" semantics is automatically guaranteed. x86 TSO Recapitulation and what's to come In this post we learned: Most of the time, shared variables are protected by locks. This has been the case since the uniprocessor days. takes advantage of this fact, and presents a much more feasible model for hardware, while maintaining the illusion of when variables are properly protected by locks. Release consistency sequential consistency Because lock acquisition can be retried, can work with weaker consistency models between synchronization ops. release consistency On x86, no memory fence is needed for locks, because the relevant instructions automatically bring order fences. This is quite a long post. And thank you for following this far. The fundamental architectural concepts are finally out of the way, in our next article, we'll switch gears and discuss some very practical topics. We'll first introduce some operating system concepts and spinlock's kin, mutex lock. We'll then look at how they perform in a very typical workload in real programming languages, pointing out potential directions for more advanced synchronization techniques.

Everything You Need to Know About Multithreading: The Realistic Release Consistency [Part 2]

You probably have heard of the idea of out-of-order execution, and that it breaks some common-sense assumptions about writing programs, and software has to insert barriers to make things right. That was a baffling concept to me at least when I heard of it. At the very least, What's the point? why would the hardware want to execute out of order only to have the software correct the behavior back? Is the software taking care of all the quirks for me?  And if not, where's the catch? Well,  all this conundrum comes from the evolution of processor design to create parallelism and the software efforts to harness the power while reining in the unwanted impact. Let's start with a tiny bit of history. Sequential consistency on uniprocessor Going back to the good old days when your CPU was just single-issue (meaning executing one instruction at a time), and there's no multi-threading programming to speak of, the programming model is straight forward -- there's memory and a stream of instructions executing in program order, doing reading/writing to the memory. For as long as the program lives, memory will reliably hold results written to it, and  reproduce the same values when read afterwards. That is, a read after a write to the same memory location will faithfully return the value written. A write after a write to the same memory location will overwrite the old value with the new. To illustrate, look at this simplistic : example1 { i = ; :: << i << ; j = ; :: << i << ; :: << j << ; i = ; :: << i << ; :: << j << ; ; } 1 # include <iostream> 2 3 int main () 4 int 1 5 std cout ' ' 6 int 5 7 std cout ' ' 8 std cout ' ' 9 2 10 std cout ' ' 11 std cout '\n' 12 return 0 13 Easy to predict, the result will be . At first variable assumes the value . Up until , where the value's updated, no matter how many times it's read the location will always return the same value. Right after 2 is written to it, reading that variable will invariably return . 1 1 5 2 5 i 1 line 9 2 There's also the variable . Since it's a different location, what value is written to it doesn't concern the output of whatsoever. j i Now let's look at a 2-threaded example to add a bit of nondeterminism. Keep in mind we're still executing on a single CPU. Imagine we have two functions and executed by two separate threads, in the following : func0 func1 example2 i = ; j = ; output[ ]; {
  i = ;
  output[ ] = j;
} {
  j = ;
  output[ ] = i;
} int 0 int 0 int 2 void func0 () 1 1 void func1 () 1 0 After the program finishes what are the valid outputs? There are roughly four instructions here. Two reads and two writes. Depending on how they are mixed, and are both likely -- if one function happens to execute before another then these will ensue. is possible too, so long as the reads are both performed after the writes are done. 01 10 11 You probably have noticed is not possible. No matter how you execute, the first instruction will be writing a to either of the output elements. 00 1 When you make this conclusion, you are of course intuitively making assumptions that the programming model is . To summarize, this means that even though the instructions from different threads may be interleaved in a nondeterministic way, each thread's execution is in program order. Also the operations are not overlapped. One memory access is done before another begins. sequential consistency Over the years, processor design has improved drastically, and computer architects play all kinds of tricks to extract parallelism from executions. For example, here in our example you may notice that in , the two operations can be performed in parallel, so long as they both execute before . Given a possible instruction sequence, we'll be free to reorder the instructions to maintain the impression that the program still runs with sequential consistency, as long as we maintain the order of memory operations to the same variable! func0 func1 Computer architects actually went ahead and took advantage of this to implement that can execute multiple instructions at a time. They tracked the operation dependencies using algorithms like and . In the history of processor you will see the architects playing nasty and nastier tricks, such as speculative execution, which caused a ton of now in the cloud business. superscalar processors Scoreboarding Tomasulo trouble But I have digressed here. The point is no matter how the system evolves, has been the contract between programmers and system builders. sequential consistency de facto Consistency model on multi-processors In the early to mid 2000's, the idea of SMP (symmetric multiprocessing) really caught on. The reason was that computer architects found it more and more difficult to dissipate the amount of heat generated by a single powerful processor. Using the same die area, they'd rather build multiple smaller "cores". However, like the uniprocessor days, in each core, instructions may still be executed out-of-order. The read-write dependencies are still tracked by the same algorithms so as to maintain the illusion that it's as if the program was still executed in-order. However, this dependency tracking won't be available across cores. Now looking back on our : example2 i = ; j = ; output[ ]; {
  i = ;
  output[ ] = j;
} {
  j = ;
  output[ ] = i;
} int 0 int 0 int 2 void func0 () 1 1 void func1 () 1 0 Suppose the two functions are executed on two separate processors, processor-0 will be free to think is all it's executing. So it's possible for this processor to read the and write the output first. Processor-1 is in the same boat! So under this paradigm, the output is actually possible! func0 j 00 To illustrate this, let's write a full-fledged program that can reproduce this: i; j; output[ ]; ::atomic< > ready; { (!ready.load()) {
  }

  i = ;
  output[ ] = j;
} { (!ready.load()) {
  }

  j = ;
  output[ ] = i;
} {
  i = ;
  j = ;
  ready.store( ); :: ; :: ; ::this_thread::sleep_for( ::chrono::milliseconds( ));
  ready.store( );

  t0.join();
  t1.join(); :: << output[ ] << output[ ] << :: ;
} { (;;)
    run_test();
} # include <atomic> # include <iostream> # include <thread> int int int 2 std bool void func0 () while 1 1 void func1 () while 1 0 void run_test () 0 0 false std thread t0 (func0) std thread t1 (func1) std std 5 true std cout 0 1 std endl int main () for Don't mind the boiler plates for now. The sleep in and the atomic are to make the two threads start roughly at the same time. run_test ready On my x86 processor, is not only possible, it's the dominant output (perhaps because reading is cheaper than writing with cache coherency protocols, which we will cover in later posts). In fact and combined only account for about 25% of the output. 00 01 10 For some reason is really rare, next to nonexistent, but that is just because of the timing of the execution. If you tell both threads to yield between the read and the write, then you will see most of the time. 11 11 Also, to illustrate this won't be a problem on uniprocessors, we can pin the two threads onto the same core by adding the following snippet right after you create the threads. Afterwards you will see output completely disappear. 00 cpuset;
  CPU_ZERO(&cpuset);
  CPU_SET( , &cpuset);
  pthread_setaffinity_np(t0.native_handle(), ( ), &cpuset);
  pthread_setaffinity_np(t1.native_handle(), ( ), &cpuset); cpu_set_t 0 sizeof cpu_set_t sizeof cpu_set_t How do we fix the broken consistency I don't know about you, but when I first saw this result my mind was blown. I knew some RISC processors can go aggressive on relaxing memory models, but I had always thought my old buddy x86 is a dependable fellow. X86 in fact, implements a memory model called TSO, or total store ordering. As the name suggests, the stores (writes) to all locations are globally ordered. More on the relaxed memory model later, but the tl;dr here is that you can imagine TSO places write results in a buffer called LSQ, or load-store-queue, before they go out to the cache. Each read afterwards will in turn check this queue for an early hit, before they themselves go out to the cache. The reason is that cache access takes much longer than register access, and it's valuable to keep a buffering structure on-core. But of course the consequence is that your read may bypass previous writes to different locations, as long as you can find a result in the LSQ, sometimes breaking sequential consistency. The fix is to enforce sequential consistency by removing the reordering. C++ gives you a standard way of doing this. Instead of declaring and as plain integers, we'll wrap them around a type, and the reads and writes will be through the and methods. i j std::atomic load() store() By default these methods will , even when these variables are accessed across different processors. So our new program will look like this: enforce sequential consistency ::atomic< > i; ::atomic< > j; output[ ]; ::atomic< > ready; { (!ready.load()) {
  }

  i.store( );
  output[ ] = j.load();
} { (!ready.load()) {
  }

  j.store( );
  output[ ] = i.load();
} {
  i.store( );
  j.store( );
  ready.store( ); :: ; :: ; ::this_thread::sleep_for( ::chrono::milliseconds( ));
  ready.store( );

  t0.join();
  t1.join(); :: << output[ ] << output[ ] << :: ;
} { (;;)
    run_test();
} # include <atomic> # include <iostream> # include <thread> std int std int int 2 std bool void func0 () while 1 1 void func1 () while 1 0 void run_test () 0 0 false std thread t0 (func0) std thread t1 (func1) std std 5 true std cout 0 1 std endl int main () for As promised before, we have now converted and into atomics. And voilà, the pattern is eliminated even if we're running on 2 cores, fully bringing us to the sequential consistency land! i j 00 Underlying the hood, the compiler inserts memory barriers so that the processors will coordinate to observe a global order on memory operations. Later on we'll get a chance to look at how the barriers are actually inserted at the assembly level. This enforcement is quite slow. If all variables are protected by memory barriers, it kind of defeats the purpose of having multiple cores. But for now, we see it solves the problem of correctness. Recapitulation and what's to come Here we have covered: Sequential consistency is the programming model computer systems strive to deliver. It's always been maintained on uniprocessor programming. When programming on multiple processors, at times programmers need to explicitly enforce sequential consistency on their own. There are language constructs programmers can take advantage of. In the next episode, we'll dig deeper into some of the more relaxed memory models and how they are supposed to be used to maintain the illusion of sequential consistency and at the same time produce as much parallelism between multiple cores as possible. Disclaimer : Compilation in this article is done with clang++ 10, with compiler flags "-O2 -std=c++20 -lpthread". YMMV as to the execution results.

Everything You Need to Know About Multithreading: Sequential Consistency Concept [Part 1]

Logistics Specialists — Serve — Are Putting Their Skills on The Blockchain All of us exchange various forms of value every single day. Whether it’s time for money or money for products and services, everyone is at once a taker and a giver. The wheels of commerce never stop spinning. Internet connectivity paved the roads of instant gratification, and most of us are happy to drive them daily. As consumers — conditioned by the advertising industry and deeply influenced by social media — we tend to lack any semblance of patience. We want things immediately, and we want them to get here on the cheap, preferably free. Because, you know, that shiny new gadget is all the shinier when it arrives on Saturday rather than Monday. And the food always tastes better if you didn’t have to fetch it on your own. Unsurprisingly, the ‘must have it now’ mentality presents unlimited opportunities for entrepreneurial ventures. A shining example is the rise of same-day deliveries. The industry is piping hot. Warm cookies and muffins, family-size meals, electronics from the Apple store, iced coffee, fine wine, and chilled beer. All of these goodies can be yours in about an hour by tapping a few buttons in an app. Overnight shipping isn’t practical for vegan smoothies, now is it? However, the logistics of satisfying our endless wants and desires can be super-tricky. Loads of moving parts make for challenging efforts of coordination. Unfairly compensating themselves are the companies behind those apps, making a killing off of our impatience. Enterprising intermediaries are seizing every chance to fleece us for the once-unfeasible services now ingrained in our everyday lives. Now, the web carried us quite far in our quest for convenience. But the blockchain can propel us even farther, trimming the fat along the way. New crypto startup — — is busy building a platform that leverages the organization’s logistical experience to create a global economy of incentivized participants. Serve You see, disintermediation creates a natural reduction in fees for every transaction within any given economy. Cut the middleman out of the equation and the rest of the players — buyers, sellers, and providers— do more winning. And on the Serve network, those winnings flow to consumers and businesses, as well as the service providers working so hard to ensure your ice cream doesn’t melt before arriving on your doorstep. Now, food delivery is only one of many industries the Serve project plans to infiltrate. We’ll cover general deliveries in this article, but it’s worth noting here that the platform intends to dive much deeper into the pools of global commerce. How exactly is the Serve project going to shake things up? Keep scrolling, and you’ll find some answers. But first, here’s a special delivery with your name on it… Disclaimer : This is not investment or financial advice. I’m not a financial expert by any stretch of the imagination. Most information within this article is speculative and merely personal opinion. Always conduct your own research before contributing to any startup projects. Always remember that what you do with your funds is your decision to make. And if that decision proves too difficult for you alone, seek guidance from a financial professional. I may or may not receive a small allocation of tokens for creating this content. That said, I do my best to remain unbiased and fair. I try to avoid all FOMO and FUD and don’t wish to evoke those emotions in my fellow crypto-heads. How to calculate the best value for online purchases Amazonian Inefficiencies Ever ordered several items from Amazon only to have them arrive in a few separate boxes? Maybe one of them was mostly air. Ugh. My toothpaste had to ride solo in there, huh? I don’t know about you, but to me, that’s the opposite of efficient. Sure, products reside in different warehouses spread across different regions. But what’s that got to do with the UPS hub making the deliveries? Shouldn’t the trigger the guys and gals in brown to assimilate before delivering? Do you really need to burn all that gas driving to my house three separate times? single order Unless I chose overnight shipping for something, slow your roll! In situations where a single online order becomes a decentralized mission of separate deliveries, I often wonder about the actual costs UPS must incur. Surely the Amazon/UPS partnership is large enough to warrant special handling of split-delivery orders. The current state of fragmentation within last-mile delivery services is an epic failure — in terms of greenhouse gases alone. Hey, UPS, can you HODL this package for us while we wait for the others to get here? Thanks, buddy. Inconvenient Truths About Postmates, Uber Eats, & Similar Platforms Over a six-month stretch of 2017, I drove bringing food and random goodies to random people. all over town I enjoy the freedom of driving, and the gig gave me access to parts of my hometown — some replete with security guards in little shacks — that I never knew existed. Now, downtime can be disastrous to your bottom line. Not long after starting to drive for one service, I added another so that the gig would, theoretically, become more profitable. Shifts began with two apps open. First come, first served. I’d often switch back and forth all shift long. On rare occasions, I’d drive solely for one service or the other, but usually both. Even with both apps active, I’d still encounter lulls, and some 4-hour shifts ended with less than $20 heading to my account. Yes, the pay for delivering food can be abysmal. Because, no, most of the extra fees customers pay won’t go to the driver. Not every customer is aware, but the system runs on tips. Without them, the gig pays . Gas and vehicle maintenance only deepen the wounds. less than minimum wage And the underlying reason for all of this insufficient compensation is the enormous fees the platforms — rather than the hardworking drivers— enjoy raking in. Many patrons are under the assumption that their driver is making more than they truly are. “I don’t need to tip since it’s already factored in,” they must tell themselves. Nope, not the case! Prices balloon because of the platform operators, not the act of delivery, which the system have. must Food-delivery platforms’ lopsided pricing structure Let me give you a real-life example. There’s a Mediterranean restaurant in my neighborhood that serves tasty gyros. I eat them so frequently I’ve memorized the post-tax, in-person price of $8.67. One rainy day found me feeling unusually tired and lazy yet hungry. I figured I’d just use Uber Eats. I opened the app, found the restaurant, and then proceeded to find my beloved sandwich. Where $7.99 once stood, $9.99 was now in its place. Yes, a 25% bump in cost. I was already aware of delivery fees plus a tip for courteous service, but this unsavory morsel of an upcharge left a sour taste in my mouth. Everyone Must Pay Now, although the customer lines the platforms’ pockets the most, the restaurants take a hit as well. As do the drivers. How Customers Get Milked Hungry eaters may think they’re only paying two fees, but in reality, there’s a trio: — Regular prices don’t apply here. Expect to pay 10–20% more for the same food that dine-in or take-out customers eat. Inflated Menu Pricing — In addition to swollen prices on menu items, we get to pay another fee for the sake of being overcharged in the first place. Service Charge — No surprises here. Somebody’s got to compensate the (hopefully) friendly driver that brings your food to wherever you are. Delivery Fee How Restaurants Get Squeezed Eateries using outside delivery services can expect to pay a service charge in exchange for the uptick in orders. In the case of Uber Eats it’s 30%. Yikes. Let’s do a little math, shall we? Our menu item is sushi-grade poke bowls. For the sake of argument, we’ll say a busy restaurant sells 200 bowls in a day. Half of the bowls stay inside, and the other half hit the road. Poke Bowl Pricing Metrics Restaurant cost = $8 Dine-in price = $20 Delivery price = $24 Service charge = 30% of gross sales In-house Orders Sales: 100 X $20 = $2,000 Cost: 100 X $8 = $800 Sales minus Cost = Profit = $1,200 Upcharged Delivery Orders Sales: 100 X $24= $2,400 Cost: 100 X $8 = $800 Service charge: $2,400 X 30% = $720 Sales minus Cost minus Service Charge = Profit = $880 Profit Difference = negative 27% So, in this example anyhow, for the privilege of using the Uber Eats service, restauranteurs pay what’s essentially a hefty tax. Every dollar that comes in sees 27 cents go right back out. Maybe it’d be worth it if a restaurant can utilize bulk prep methods to trim costs. However, to give up 27% of profits is a steep ask. One wonders if the eatery wouldn’t be better off spending the same — or even less — on a marketing campaign. Even though owners feel the pinch of steep fees, it’s hard to ignore the extra revenue they otherwise wouldn’t have. Tough choice for some restaurant owners, no doubt. But reason enough for the owner of a local Vietnamese bánh mì sandwich spot to deny the platform’s courtship attempts. How Drivers Get Burned The logistics of the Uber Eats operation are far from perfect. Aside from getting only a portion of any delivery fee, drivers must contend with long wait times due to inefficiencies. Sometimes it’s a fun little glitch where the app assigns the same order to two different drivers. Upon arrival, the last driver hears their order is already out the door. So I drove all the out here for nothing then? Thanks! For the uninformed, most food deliverers are paid by the order, not by the hour. Aside from wasting gas and mileage, losing time that could be better spent making actual deliveries can be especially costly. And while the platforms can be detrimental to a driver’s earnings, the restaurants themselves are often to blame. Home of the Big Mick I can honestly tell you that, after completing over 1K deliveries, WacArnold’s is the worst offender of them all. The situation was so ugly that I’d immediately cancel any orders from that “restaurant” appearing on my app. You see, with the rare exception of an all-star manager, Mickey D’s employees HATE orders from Uber Eats. Why? Because Uber orders arrive on a separate terminal tucked away near a register off to the side somewhere. Detachment from the main flow of burgers and fries spills a heaping helping of WacFlurry all over the whole operation. Here’s an actual conversation I had with a visibly flustered employee whose name tag read Bill: Bill: What can I get for you? Me: “Hi. How are you doing this evening?” Bill: “Oh, I’m a little stressed.” Me: “Sorry to hear that. I’m here to pick up an order for Uber Eats.” Bill: “That’s why I’m stressed.” Orders are often forgotten and not entered until “the Uber” shows up. Yep, they really called me that on multiple occasions at multiple locations. Someone announces to the rest of the crew, “the Uber’s here!” after Standing around waiting for a greasy brown bag — or unplaced orders from any other joint — cuts deeply into a driver’s earnings. What’s more, let’s not ignore the trickle-down effect of a small or non-existent tip because the order took so long getting to the customer. Yes, on-demand delivery services are convenient. Who doesn’t want excellent food or handy gadgets on the quick? But at the same time, they’re needlessly overpriced. The on-demand delivery industry’s not going anywhere. We all get hungry — for food or practically everything imaginable — every single day. However, we can do it better, and we can do it cheaper by putting the operation onto a blockchain. Now that you’re fully aware of why the system is so costly, let’s examine how the Serve project aims to improve the entire experience… The Serve platform’s economy runs on SRV tokens Tokens Can Crush Costs The Serve platform runs on its native SRV token. The same tokens power smart contracts, which fuel network transactions. Swerve chose to bake an escrow system into transactions. All parties must uphold their end of the agreement before a transaction settles. Customers pay for goods and services with SRV tokens, but businesses and deliverers must also stake tokens. Think of the concept as the ante in a round of poker. You need a stake in the pot, or else you don’t get to play. Once the smart contract agrees that everything’s in order, the rightful share of the transaction’s SRV tokens returns home to originating wallets. By removing the element of human trust — one reason why blockchain tech exists in the first place — we’re alleviating the need to involve us bumbling mistake-machines every step of the way. The platform can effectively eliminate bloated fee structures by placing trust in an automated system. We’re putting our faith in programming rather than forgetful Frank in the shipping dept. Perhaps I needn’t go so far as to use the term “faith” in the first place. Transparency is the name of the game, and by having a public display of everything that’s happening within digital transactions, the element of trust becomes indisputable. Bad actors don’t stay bad for long because the blockchain calls them out on any shenanigans they try to pull. Furthermore, economies based on tokens are inherently cost-effective. We’re merely outsourcing jobs to computers — the ultimate accounting bots. Now, before you get all “they took our jobs!” on me, you’ve got to admit that some tasks are best left to algorithms. Crunching data and storing immutable information are two prime examples. And on the Swerve platform, fees top out at 2.5%. If we assume a 25% average fee for the world’s various delivery platforms, that’s a 10X decrease! Everyone Must Win Serve aims to improve the multitude of last-mile delivery services, no doubt. But they’re not taking an aggressive, ‘eliminate the competition’ approach. Instead, they invite anyone to integrate with their open-source protocol. The goal is to create industry-wide standards that everyone adopts. The project is basically saying, “look, our current systems and processes need help. We’re experts in logistics, but there are others out there, too. Let’s work together to create a uniform system for everyone’s betterment.” Now, compared to today’s offerings, the Serve platform’s participants — enterprises, drivers, and customers — gain a massive reduction in fees. But let’s check into some of the other benefits a global logistics platform can deliver… How Drivers Gain Endless Possibilities When the drivers win, there’s a domino effect that makes its way to the businesses and customers too. I’m living proof of the high turnover rate among on-demand delivery drivers. Translation: Plenty of people out there aren’t exactly doing their best work. Your heart’s not in it when you’re on the verge of quitting. Serve created a video about my former self. How did they even know? Had this situation been reality last year, I would’ve stayed in the game longer. My name’s not Alex, but his virtual situation was mine in the real world… Me, a year ago Driving while listening to directions, hunting for addresses, and actively monitoring two separate apps is distracting at best and dangerous at worst. Especially the secondary app scenario since it requires physical interaction with your phone while the vehicle’s in motion. Imagine five of the significant incumbents tying into the Serve protocol. A driver could drive for all of them yet operate from a single interface. Essentially, a simplistic, centralized, token-earning solution. Downtime shrinks to practically nothing because everywhere you go in a major city, at any time of day, somebody wants food, a product, or a ride. Not to mention obviating the hassle of creating additional accounts and linking bank accounts and submitting insurance information. Well-paid drivers are bound to stay on the road longer. Should the Serve platform see some big names jump aboard, making deliveries in your own vehicle becomes much more lucrative. How Businesses Earn Higher Profits Similar to drivers being able to grab work for many services at once, business owners can enjoy the same luxury. The Serve project offers enterprise solutions — including APIs & SDKs — which enable companies to put some of their business operations on the blockchain. By enrolling with Serve, they’re putting an army of drivers to work for them. No relying on a specific service’s delivery force to grab your goods because the Serve driver is ready to roll. nearest On the food side, more drivers mean food flying out the door nearly as fast as you can make it. And, since the fees are so low, the decision to enroll should prove simplistic. How Customers Get Faster Service Tying back into the large volume of drivers ready to whisk a bottle of whiskey straight to your location, wait times for anything and everything can realize a significant reduction. Place an order for something and, no matter which delivery service umbrella a driver falls under, your items get to you in a hurry. Speedy service coupled with low prices keeps customers returning to the Serve platform again and again. Which is also good for the drivers and business owners. Do you see the circle of self-feeding efficiency at work here? Happy customers make happy business owners and busy drivers. Win/win/win! Final thoughts… Cryptocurrencies give us — as responsible, sovereign individuals with the wherewithal to handle our own monetary transactions — the power to have a voice beyond the realm of fiat. Admittedly, the current state of affairs is the equivalent of the lone cry from the microscopic planet of Whoville. However, given time, our collective shouts will garner the attention of big-name players will ignore tokens at their peril. As crypto enthusiasts, we’re in the minority. Most people merely can’t see the benefits. But eventually, we’ll be so loud that the outsiders will have to enter our realm. I can foresee the same scenario playing out within the last-mile delivery space. A transparent and efficient set of industry standards attracts any business looking to run a tighter ship. Namely, all of them. And, there’ such a wealth of multi-billion-dollar industries the project is courting. Small percentages of market share in any given industry are perfectly acceptable because of their collective potential. The Serve project is one to keep both eyes on. The team’s ambitions seem boundless, and they’re out to solve some genuine problems — on a global scale — that most of us deal with on the regular. I, for one, anticipate the day when the middleman stops overcharging for the epitome of convenience — anything and everything, brought to wherever you are. DYOR Now, just because I’m bullish on project Serve doesn’t mean you need to jump right in. It’s always important to form your own opinion. And, conveniently, here are a few places you can do just that: Serve Website Serve Whitepaper — Scoobeez The Serve team’s existing delivery service 👇 👇 Get Social with Serve Bitcointalk | Facebook | GitHub | Instagram | LinkedIn | Medium | Reddit | Telegram | Twitter | YouTube By the way… If you like what you see here and need help getting your crypto message to the masses, I’d love to hear about your startup. Even if you just want to chat about crypto or your favorite blockchain projects, you can find me here: blockchainauthor at Gmail Bounty0x username = blockchainauthor

How Tokenization Can Curb the Costs of Our Insatiable Appetite for On-Demand Everything Now

The type class patterns are simple but useful. I’ll walk through some examples. Has surprisingly Use Case 1: Collecting all Images Imagine you are working on a game and during an asset validation step, you want to make sure that the scene’s images exist. We need to traverse the scene and collect all the image file paths. Let’s make a type: description Scene data Scene = Scene{ backgroundImage   :: Text, characters        :: [Character], bewilderedTourist :: Maybe Character, objects           :: [Either Rock WoodenCrate]} data Character = Character{ hat   :: Maybe DamageArray, head  :: DamageArray, torso :: DamageArray, legs  :: DamageArray, shoes :: Maybe DamageArray} data DamageArray = DamageArray{ noDamage        :: Text, someDamage      :: Text, excessiveDamage :: Text} data Rock = Rock{ weight    :: Double, rockImage :: Text} data WoodenCrate = WoodenCrate{ strength         :: Double, woodenCrateImage :: DamageArray} You get the idea. There are a lot of types, with a fair amount of nesting. A real scene could have hundreds of types and double digit levels of nesting, but this is a good enough example for our purposes. So now we want to write a function, . collectImages :: Scene -> Set Text You haz no Has The most straightforward approach is to just write the functions: collectImages :: Scene -> Set TextcollectImages Scene {..}=  singleton backgroundImage<> mconcat (map collectCharacterImages characters)<> maybe mempty collectCharacterImages bewilderedTourist<> mconcat (map (either (singleton . collectRockImage)collectWoodenCrateImages)objects) collectCharacterImages :: Character -> Set TextcollectCharacterImages Character {..}=  maybe mempty collectDamageArrayImages hat<> collectDamageArrayImages head<> collectDamageArrayImages torso<> collectDamageArrayImages legs<> maybe mempty collectDamageArrayImages shoes collectDamageArrayImages :: DamageArray -> Set TextcollectDamageArrayImages DamageArray {..} = fromList[ noDamage, someDamage, excessiveDamage] collectRockImage :: Rock -> TextcollectRockImage Rock {..} = rockImage collectWoodenCrateImages :: WoodenCrate -> Set TextcollectWoodenCrateImages WoodenCrate {..} =collectDamageArrayImages woodenCrateImage The code is verbose and a little tedious, but not terribly difficult to write or follow. I was disciplined and named everything in a consistent way, which made it easy remember. The trickiest part is just remembering what helper functions to call when operating on my polymorphic containers (all the s and stuff). maybe mconcat All the Has in the World Here is the same code written with a variation of the type class pattern: Has class HasImages a whereimages :: a -> Set Text instance HasImages a => HasImages [a] whereimages xs = foldr (\x accum -> images x <> accum) mempty xs instance HasImages a => HasImages (Maybe a) whereimages x = maybe [] images x instance (HasImages a, HasImages b) => HasImages (Either a b) whereimages x = either images images x instance HasImages Scene whereimages backgroundImage<> images characters images bewilderedTourist<> images objects Scene {..}        =  singleton <> instance HasImages Character whereimages Character {..}=  images hat<> images head<> images torso<> images legs<> images shoes instance HasImages DamageArray whereimages DamageArray {..} = fromList[ noDamage, someDamage, excessiveDamage] instance HasImages Rock whereimages Rock {..} = singleton rockImage instance HasImages WoodenCrate whereimages WoodenCrate {..} = images woodenCrateImage Alright, so this the simplest variation of the type class pattern. We have a type class which requires a function, , to be implemented by each instance. Has HasImages a -> Set Text The first difference between the example and the prior example is that I have implemented generic functions for my polymorphic containers , , and . The value in this approach is that I don’t have to think about what functions to call to collect the images: it’s always . In the prior example, I had to think about the how to collect the images each time, and it took brain power better spent elsewhere. Has [] Maybe Either images The benefits of the pattern are: Has I can write a single instance for each polymorphic container that will work for all specializations I need. I do not have to make as many decisions, freeing up brain power to focus on other things It provides structure for other engineers to extend without having to make decisions about names of functions and what the type the functions should be (see the inconsistency from the first example). collectRockImage The downsides are: It uses a type class, which is a more complicated concept than a function. 2. The instance declaration is noisier than the function declaration and required greater indention. Use Case 2: Composable Reader The pattern can also be used to create a composable Reader monad. Has Say you have library A with the following: foo :: Reader Int Bool and library B with: bar :: Reader String Int and you would like to be able to write foobar = doflag <- foo if flag thenbarelsereturn 0 but it won’t type check, because needs an environment and needs a environment. foo Int bar String The trick is to define the helper type classes: Has class HasFooEnv a wheregetFooEnv :: a -> Int class HasBarEnv a wheregetBarEnv :: a -> String Then we modify the type signatures to use : MonadReader foo :: (MonadReader e m, HasFooEnv e) => m Bool We will have to modify calls to to use . We make a similar modification for : ask asks getFooEnv bar bar :: (MonadReader e m, HasBarEnv e) => m Int and instances: instance HasFooEnv (Int, String) wheregetFooEnv = fst instance HasBarEnv (Int, String) wheregetBarEnv = snd We get the combined version to type check: foobar :: Reader (Int, String)foobar = doflag <- foo if flag thenbarelsereturn 0 Michael Snoyman also discusses the pattern in a post on ReaderT . Has here Use Case 3: Convenient Argument Passing It is quite common in database applications to have the following types: newtype Key a = Key UUIDdata Entity a = Entity{ entityKey   :: Key a, entityValue :: a} Additionally, one will write queries that look like: getFriends :: Key User -> [Entity User] which will get called often by extracting a from an . Key User Entity User getFriends (entityKey user) and you can make the API just ever so slightly easier to use with: class HasKey a k | a -> k wherekey :: a -> Key k instance HasKey (Key a) a wherekey = id instance HasKey (Entity a) a wherekey = entityKey getFriends :: HasKey a User => a -> [Entity User] and one can now pass in either a or . Entity User Key User getFriends user It’s a small thing, but one of my past coworkers liked it and I do myself so I’m including it. More difficult error messages is a downside. Use Case 4: Traversals So far we are discussing a simple version of that can only get things. This is only the beginning. Going back to our first example, let’s say that instead of merely collecting the images, we also want to traverse the scene and update the image file paths with the hash of the image as a suffix. Has We are going to take advantage of the package and our new class will look like: lens HasImages class HasImages a whereimages :: Traversal' a Text Our instances look like: instance HasImages a => HasImages [a] whereimages = traversed . images instance HasImages a => HasImages (Maybe a) whereimages = traversed . images instance (HasImages a, HasImages b) => HasImages (Either a b) whereimages f e = case e ofLeft  x -> Left  <$> traverseOf images f xRight x -> Right <$> traverseOf images f x instance HasImages Scene whereimages f Scene {..}=  Scene<$> f backgroundImage<*> traverseOf images f characters<*> traverseOf images f bewilderedTourist<*> traverseOf images f objects instance HasImages Character whereimages f Character {..}=  Character<$> traverseOf images f hat<*> traverseOf images f head<*> traverseOf images f torso<*> traverseOf images f legs<*> traverseOf images f shoes instance HasImages DamageArray whereimages f DamageArray {..}=  DamageArray<$> f noDamage<*> f someDamage<*> f excessiveDamage instance HasImages Rock whereimages f Rock {..}=  Rock weight<$> f rockImage instance HasImages WoodenCrate whereimages f WoodenCrate {..}= WoodenCrate strength<$> traverseOf images f woodenCrateImage We can apply our hash updater like: hashFilePath :: Text -> IO TexthashFilePath filePath = dolet pathStr = T.unpack filePathfileHash <- hashBytes <$> BSL.readFile pathStrreturn $ T.pack $ dropExtension pathStr++ "-" ++ fileHash <.> takeExtension pathStr hashSceneImages :: Scene -> IO ScenehashSceneImages x = traverseOf images hashFilePath x Not only that, but we get our for “free” (although the performance is going to be different, which probably doesn’t matter). collectImages collectImages :: Scene -> [Text]collectImages x = fromList $ toListOf images x Use Case 5: Composable State We can get a composable State monad like we got a composable Reader monad by using a instance of simple function: Lens class HasFooState a wherefooState :: Lens' a Int class HasBarState a wherebarState :: Lens' a String then we modify the type signatures to use : MonadStates foo :: (MonadState s m, HasFooState s) => m Bool We will have to swap calls to with , calls to with and becomes . We modify in a similar way: get use fooState modify modifying fooState put assign fooState bar bar :: (MonadReader s m, HasBarState s) => m Int and instances: instance HasFooState (Int, String) wherefooState = _1 instance HasBarState (Int, String) wherebarState = _2 We get the combined version to type check. foobar :: State (Int, String)foobar = doflag <- foo if flag thenbarelsereturn 0 Use Case 6: Extendible Exceptions Basing the class on s allows us to have extendible exceptions with . Has Prism MonadError Our class will look like: class HasIdNotFound a where_IdNotFound :: Prism a UUID We then write our functions like: foo :: (HasIdNotFound e, MonadError e m) => m a and can throw our exceptions by calling: throwError $ review _IdNotFound theId For a more complicated variant that requires fewer instances, take a look at this . post A Magical Alternative If you’re like me, you’re probably wondering if there was some magical way to write and without doing any work. There is! We can use (or another similar library). collectImages hashSceneImages [uniplate](https://hackage.haskell.org/package/uniplate-1.6.12/docs/Data-Generics-Uniplate-Data.html) We need to enable and add a to each type. Then our becomes: DeriveDataType deriving (Data) collectImages import Data.Generics.Uniplate.Data collectImages :: Scene -> Set TextcollectImages x = fromList (universeBi x) and our is now: hashSceneImages hashSceneImages :: Scene -> IO ScenehashSceneImages x = transformBiM hashFilePath x The downside to this approach is it indiscriminately collects all values. This is not necessarily what we want (we could make a to make it safer). Another downside is it is slower than a custom traversal class. Text newtype ImageFile = ImageFile Text Conclusion type classes are simple, but they can keep your code well-structured and help you tackle common tasks. Additionally, you might be able to YOLO it with . Has uniplate The repo with more complete examples . here is how hackers start their afternoons. We’re a part of the family. We are now and happy to opportunities. Hacker Noon @AMI accepting submissions discuss advertising & sponsorship To learn more, , , or simply, read our about page like/message us on Facebook tweet/DM @HackerNoon. If you enjoyed this story, we recommend reading our and . Until next time, don’t take the realities of the world for granted! latest tech stories trending tech stories

Stories, News & Mentions about UNIPLACES

Uniplaces’s Stories on HackerNoon