<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Martin Stypinski on Medium]]></title>
        <description><![CDATA[Stories by Martin Stypinski on Medium]]></description>
        <link>https://medium.com/@Styp?source=rss-3ab3e769942e------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*GQ_fvfIO43sFlkz-W_Nwpw.png</url>
            <title>Stories by Martin Stypinski on Medium</title>
            <link>https://medium.com/@Styp?source=rss-3ab3e769942e------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 10:09:30 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@Styp/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Navigating the Challenges of ML and Satellite Imaging]]></title>
            <link>https://medium.com/@Styp/navigating-the-challenges-of-ml-and-satellite-imaging-8236385bf336?source=rss-3ab3e769942e------2</link>
            <guid isPermaLink="false">https://medium.com/p/8236385bf336</guid>
            <category><![CDATA[remote-sensing]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[earth-observation]]></category>
            <category><![CDATA[gis]]></category>
            <category><![CDATA[satellite-imagery]]></category>
            <dc:creator><![CDATA[Martin Stypinski]]></dc:creator>
            <pubDate>Fri, 09 Aug 2024 14:24:13 GMT</pubDate>
            <atom:updated>2024-08-09T14:24:13.922Z</atom:updated>
            <content:encoded><![CDATA[<p>Originally published on <a href="https://www.linkedin.com/pulse/navigating-challenges-ml-satellite-imaging-martin-stypinski-hw5qe/?trackingId=4wt2uOMoTP6kUIBZoFV6Ug%3D%3D">Linkedin</a>.</p><p>In today’s fast-evolving technological landscape, more and more use cases enable whole industries to capture new value through innovative solutions to enhance decision-making, risk assessment, and operational efficiency.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/911/1*ghr3TOjl9LmtwDqQoj9lgw.png" /><figcaption>Source: Generated by Dall-E from OpenAI with an own prompt.</figcaption></figure><p>In recent years, I have worked on integrating Computer Vision (CV) with various types of media (images, video, medical scans, etc.). A very exciting medium to analyse is satellite images. After a few projects, CV with satellite images seems to be emerging as an enhancing tool, offering unprecedented capabilities with little operational risks (when done right).</p><p>With this piece, I want you, as reader, to challenge me or get inspired about use cases and find out the challenges there are when trying to apply CV to satellite images. Generally, there are use cases in different industries, such as defense, agriculture, real estate, urban planning and many more.</p><h3>Overview</h3><p>Why does CV in satellite images matter? There are many use cases of CV that can help improve current tasks. Therefore, I will start by outlining what CV can actually do and mention a few use cases.</p><p>To get a deeper understanding of what is possible, one needs to understand the types of satellite images that exist. From recent projects, I have learnt that identifying and selecting the right type of images is crucial to get an effective and accurate model. Note: Accuracy of models are the north star metric of ML models for any use case, in my experience.</p><p>Last, but not least, I outline the technical and operational challenges of such an ML project. Consultants often overpromise and target the multi-million dollar project, but do not de-risk the project for clients by identifying hurdles early. Finding clever ways to mitigate hurdles is exponentially more important with ML and CV projects than for normal software development projects, due to their complexity and high operational costs.</p><h3>Tasks Computer Vision and Machine Learning Excels In</h3><p>Applying CV to satellite images provides a multitude of use cases and listing all of them here would be an overkill. What I can do, is list the tasks that CV can actually do and make examples of use cases. I am curious to learn from readers, which use cases you have observed or have worked on, already.</p><ol><li><strong>Change Detection:</strong> Beyond identifying alterations, advanced algorithms can now quantify changes, providing metrics on the extent of alterations in landscapes and infrastructure. Use Case: Monitoring progress or illegal changes in infrastructure construction.</li><li><strong>Pattern Recognition:</strong> Modern CV techniques go beyond simple pattern analysis to predictive modeling, forecasting potential future changes based on historical data. Use Case: Identifying environmental trends or trends in urban planning.</li><li><strong>Object Identification:</strong> Detection and classification of objects in complex environments, such as identifying specific vehicle types or infrastructure elements, crucial for granular asset monitoring and intelligence gathering. Use Case: Proof of damage or existence for insurance-related claims; recognize movable objects from space (depending on object size).</li><li><strong>Image Enhancement:</strong> Techniques such as super-resolution and de-noising transform low-quality images into higher-resolution versions, essential for analyzing areas where high-resolution data is not available or is cost-prohibitive to obtain. Use Case: Increase revenue with higher resolution satellite images for satellite image providers. Optimize costs for image acquisition for a specific use case.</li><li><strong>Anomaly Detection:</strong> Identifying unusual patterns or outliers that deviate from normative data that are crucial for early warning systems in environmental monitoring, security breaches, or identifying areas at risk of natural disasters. Use Case: Early warning signs for floods or bushfires starting in remote areas.</li><li><strong>Semantic Segmentation:</strong> Segmenting satellite images into meaningful categories such as water, urban, forest, etc., provides detailed land use and cover maps that are invaluable for environmental conservation and agricultural monitoring. Use Case: Forest management campaigns for sustainability initiatives. Automatic Land-use classification.</li></ol><p>Unfortunately, many of these use cases will not succeed, if only RGB satellite images are used to train the model. Applying other types of satellite images, enable more accurate models and therefore more real use cases. Not only for marketing purposes.</p><h3>Increasing accuracy and quality of results</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/0*ZJKGK-QI8VMEzHlW" /><figcaption>Source: Generated by Dall-E from OpenAI with an own prompt.</figcaption></figure><p>Now, increasing the accuracy of above tasks, is difficult. CV models require a lot of data. But satellite images are satellite images, right? Lucky enough for your project, no. Most people relate to satellite images as RGB color images, as seen in Google Maps, Bing, etc. But most satellites acquire way more information than the human visible three-channel RGB bands. Meaningful insights can not only be extracted by remote sensing experts but also by applying state of the art ML models. The bands of visual and non-visual data contain:</p><ol><li><strong>RGB:</strong> Captures the light across the spectrum of the human eye.</li><li><strong>Multispectral:</strong> Captures light across specific bands of the electromagnetic spectrum, including both visible and invisible light (e.g. near-infrared, mid-infrared).</li><li><strong>Hyperspectral:</strong> Similar to multispectral, but captures a much broader spectrum, with narrow bands, providing detailed information about the material properties of the Earth’s surface.</li><li><strong>Panchromatic:</strong> Black and white imagery that offers higher spatial resolution compared to multispectral images. It mostly combines red, blue, and green channels to enhance resolution, producing a black and white image with higher resolution to estimate surface brightness.</li><li><strong>Thermal infrared:</strong> Captures thermal radiation emitted from the Earth’s surface, useful for measuring surface temperatures.</li><li><strong>Radar:</strong> Uses synthetic aperture radar to produce images, independent of daylight and weather conditions.</li></ol><p>Then, there are already manipulated image types (or different acquisition protocols) that are widely available, such as:</p><ul><li><strong>LiDAR:</strong> Although not a traditional “image,” LiDAR data collected by satellites create high-resolution 3D representations of the Earth’s surface.</li><li><strong>Normalized Difference Vegetation Index:</strong> A computed index using visible and near-infrared light to assess vegetation health. Synthetically generated data based on the red and infrared channel information.</li><li><strong>False Color:</strong> Manipulates or combines various spectral bands to highlight specific features such as vegetation, water bodies, or urban areas.</li><li><strong>Water Vapor:</strong> Captures data related to the presence and movement of water vapor in the atmosphere.</li></ul><p>The vastness of available types of images is a gain and a pain. The gain is that it enables one to feed a model with more data, which can lead to higher model accuracy. Again, businesses need high accuracy in order to generate model-driven value. Why? People can base their decision on this data and trust it is accurate.</p><p>The pain is that one cannot just combine all types of images. You need to combine the right ones and test which combination generates the highest accuracy with the least data and therefore the least power to train the model. And let me tell you… you need a lots of computing power!</p><h3>Implementation Challenges</h3><p>Now, this all sounds good like ChatGPT, but the real challenge lies in the implementation of these use cases. I am not a fan of immediate large million-dollar projects, because they end up wasting a lot of money at the wrong places and discourage businesses to innovate and generate more value (maybe I should start, though).</p><p>To de-risk the innovation journey and enable better business and technology decision-making, I prefer verifying everything that could go wrong and could be a show-stopper early on in a project. This helps ensure technical feasibility and provides information to businesses to calculate the business case.</p><p>This is why you get a list of challenges and methods on how to solve them:</p><p><strong>1. Data Volume and Management:<br></strong>The vast amount of satellite data demands robust data management strategies and scalable processing capabilities.</p><p><strong>Approaches:</strong></p><ul><li><strong>Verify Small:</strong> Try to verify models on small datasets and figure out the feasibility and value impact.</li><li><strong>Think Big:</strong> Stay ambitious and think big — lots of data is proven to solve lots of challenges.</li></ul><p><strong>2. Integration with Existing Systems:<br></strong>Merging CV insights with legacy systems can be daunting, given the variance in data formats and operational paradigms.</p><p><strong>Approaches:</strong></p><ul><li><strong>APIs &amp; Microservices:</strong> Develop APIs that allow for the smooth integration of CV insights into existing workflows, ensuring minimal disruption.</li><li><strong>Custom Adapters:</strong> Create custom adapters that act as intermediaries, translating CV data into formats understandable by legacy systems.</li></ul><p><strong>3. Scalability:<br></strong>The ability to scale operations as data volume and processing needs grow is crucial.</p><p><strong>Approach:</strong></p><ul><li><strong>Modular Architecture:</strong> Design system architectures that are inherently scalable, allowing for the addition of resources without extensive re-engineering.</li></ul><p><strong>4. Interoperability:<br></strong>Ensuring that CV systems can communicate and operate with other systems and technologies is essential for holistic insights.</p><p><strong>Approach:</strong></p><ul><li><strong>Standards Adoption:</strong> Adhere to industry standards for data and communication to ensure interoperability across different platforms and systems.</li></ul><p>I am not covering the skills gap and regulatory challenges in this list, because I am not an expert on these, but I am aware that they are essential on this type of projects.</p><h3>Summary</h3><p>The synergy between CV and satellite imagery improves how industries assess risks, identify changes or anomalies, manage assets, and identify fraud. The dropping cost in computing power, the vast availability of powerful algorithms and the availability of satellite images, makes many business cases profitable.</p><p>This will invite people to see potential everywhere and start cutting corners. In comparison to digitalization and statistical challenges, ML applications are the 3D version of chess. Yes, the potential is huge, but diligence is even more important to create real value.</p><p>So, in short: <em>Satellite images include more information than one might think and combining them is a treasure trove for different industries.</em></p><p>If you have a use case that you would like to discuss, contact me at <a href="/service/mailto:martin@veemg.com">martin@veemg.com</a> or via DM on <a href="https://www.linkedin.com/in/styp/">LinkedIn</a>.</p><p>This article was written by me, <a href="https://www.linkedin.com/in/styp/">Martin Stypinski</a>, and <a href="https://www.linkedin.com/in/philipwels/">Philip Wels</a>.<br>Cross-published on LinkedIn (<a href="https://www.linkedin.com/pulse/navigating-challenges-ml-satellite-imaging-martin-stypinski-hw5qe/?trackingId=4wt2uOMoTP6kUIBZoFV6Ug%3D%3D">https://www.linkedin.com/pulse/navigating-challenges-ml-satellite-imaging-martin-stypinski-hw5qe/?trackingId=4wt2uOMoTP6kUIBZoFV6Ug%3D%3D</a>).</p><p>The following people inspired us to write this article, based on their research and their articles:</p><p>Nejc Vesel, Grega Milcinski, Matej Aleksandrov, Matej Batič, Nika Oman Kadunc, Devis Peressutti, Sara Verbič, Andrew Joseph Davies, Sharada Prasanna Mohanty, Jakub Czakon 🍐, Kamil A. Kaczmarek, Andrzej Pyskir, Piotr Tarasiewicz, Saket Kunwar, Janick Rohrbach, Dave Luo, Manjunath Prasad, Sascha Fleer, Jan Philip Göpfert, Akshat Tandon, Guillaume Mollard, Nikhil Rayaprolu, Marcel Salathe, Malte Schilling, Xiangyu Chen, Xintao Wang, Jiantao Zhou, Yu Qiao, Chao Dong Bee, Lim Sanghyun Son, Heewon Kim, Seungjun Nah, Kyoung Mu Lee, Julien Cornebise, Ivan Oršolic, Freddie Kalaitzis, Zhihao Wang, Jian Chen, Steven C.H. Hoi, Chen Change Loy, Kaiming He, Xiaoou Tang, Ying-Nong Chen, Kuo-Chin Fan, Yang-Lang Chang, Toshifumi Moriyama, Justin Johnson, Alexandre Alahi, Li Fei-Fei and more.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=8236385bf336" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Why loops do matter — A Story of Matrix Multiplication, Cache Access Patterns and Java]]></title>
            <link>https://medium.com/@Styp/why-loops-do-matter-a-story-of-matrix-multiplication-cache-access-patterns-and-java-859111845c25?source=rss-3ab3e769942e------2</link>
            <guid isPermaLink="false">https://medium.com/p/859111845c25</guid>
            <category><![CDATA[performance-improvement]]></category>
            <category><![CDATA[java]]></category>
            <category><![CDATA[matrix-multiplication]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Martin Stypinski]]></dc:creator>
            <pubDate>Mon, 25 Sep 2023 14:37:13 GMT</pubDate>
            <atom:updated>2023-09-25T14:44:53.371Z</atom:updated>
            <content:encoded><![CDATA[<h3>Why loops do matter — A Story of Matrix Multiplication, Cache Access Patterns and Java</h3><h4>Exploring Java matrix multiplication: Cache optimizations often overlooked in basic algorithms for performance gains.</h4><h4>Introduction</h4><p>This article will explore several simple options but different implementations of squared matrix multiplications in plain Java. The results demonstrate that we occasionally overlook cache locality and cache strides in basic algorithms, leading to missed opportunities for performance improvements.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*JG5j5MT3xe3_vGRmPepnAg.png" /><figcaption>Small changes, big impact — Java code runs like Schnell! (I can’t use rockets anymore; used them too often.)</figcaption></figure><h4>Wait, why are we doing this?</h4><p>For many experienced engineers, this is a very straightforward topic, and the answer is obvious. Personally, this is journalling for completeness&#39; sake to find a meaningful baseline for my upcoming Java Vector API Matrix Multiplication article. I just want to take a minute and reflect on some effects to show a meaningful uplift (in my upcoming article), not an uplift that is partly induced by better cache locality through rewriting my code.</p><h4>Methodology</h4><p>As in some previous work, the 2D squared matrix is represented in a 1D array. For those of you who are unaware of this concept, I recommend reading my last article: <a href="https://medium.com/@Styp/observing-java-19-jvm-optimization-with-jmh-hsdis-perfasm-holy-trinity-of-low-level-9bd1daecf1b3">https://medium.com/@Styp/observing-java-19-jvm-optimization-with-jmh-hsdis-perfasm-holy-trinity-of-low-level-9bd1daecf1b3</a></p><p>To use consistent terminology, we designate three variables:<em> i, j, and k,</em> for the three loops needed to perform a simple O(n^3) squared matrix multiplication.</p><p>The most basic implementation is therefore the IJK-multiplication:</p><pre>  public float[] baselineIJK(float[] a, float[] b, float[] result, int n) {<br>      for (int i = 0; i &lt; n; i++) {<br>          for (int j = 0; j &lt; n; j++) {<br>              float sum = 0.0f;<br>              for (int k = 0; k &lt; n; k++) {<br>                  sum += a[i * n + k] * b[k * n + j];<br>              }<br>              result[i * n + j] = sum;<br>          }<br>      }<br>      return result;<br>  }</pre><p>In order to get all combinations, the variables <em>i, j, and k </em>can be permuted, resulting in 6 different combinations; here are the five additional ones:</p><pre>public float[] baselineJIK(float[] a, float[] b, float[] result, int n) {<br>    for (int j = 0; j &lt; n; j++) {<br>        for (int i = 0; i &lt; n; i++) {<br>            float sum = 0.0f;<br>            for (int k = 0; k &lt; n; k++) {<br>                sum += a[i * n + k] * b[k * n + j];<br>            }<br>            result[i * n + j] = sum;<br>        }<br>    }<br>    return result;<br>}<br><br>public float[] baselineIKJ(float[] a, float[] b, float[] result, int n) {<br>    for (int i = 0; i &lt; n; i++) {<br>        for (int k = 0; k &lt; n; k++) {<br>            float aik = a[i * n + k];<br>            for (int j = 0; j &lt; n; j++) {<br>                result[i * n + j] += aik * b[k * n + j];<br>            }<br>        }<br>    }<br>    return result;<br>}<br><br>public float[] baselineKIJ(float[] a, float[] b, float[] result, int n) {<br>    for (int k = 0; k &lt; n; k++) {<br>        for (int i = 0; i &lt; n; i++) {<br>            float aik = a[i * n + k];<br>            for (int j = 0; j &lt; n; j++) {<br>                result[i * n + j] += aik * b[k * n + j];<br>            }<br>        }<br>    }<br>    return result;<br>}<br><br>public float[] baselineJKI(float[] a, float[] b, float[] result, int n) {<br>    for (int j = 0; j &lt; n; j++) {<br>        for (int k = 0; k &lt; n; k++) {<br>            float bjk = b[k * n + j];<br>            for (int i = 0; i &lt; n; i++) {<br>                result[i * n + j] += a[i * n + k] * bjk;<br>            }<br>        }<br>    }<br>    return result;<br>}<br><br><br>public float[] baselineKJI(float[] a, float[] b, float[] result, int n) {<br>    for (int k = 0; k &lt; n; k++) {<br>        for (int j = 0; j &lt; n; j++) {<br>            float bjk = b[k * n + j];<br>            for (int i = 0; i &lt; n; i++) {<br>                result[i * n + j] += a[i * n + k] * bjk;<br>            }<br>        }<br>    }<br>    return result;<br>}</pre><p>Upon closer examination of the code pieces, there are similarities between all the methods. Two of the six implementations are always the same, resulting in three groups, ending with the index i, j, or k, accordingly. The outer loops don’t have the same impact on cache access compared to the most inner loops. These combinations result in the following tuples:</p><ul><li>IJK and JIK</li><li>KIJ and IKJ</li><li>JKI and KJI</li></ul><p><strong>A short excursion into Caches:<br></strong>After grouping the three options, we need to look into the CPU’s cache and our array representation in memory. Later, we can make some assumptions about the runtime performance of each variant.</p><p>First, the ALU requires data to execute instructions on the provided data. If data is not available, the ALU will experience a stall. Within the CPU, different mechanisms try to avoid an ALU stall. Modern architectures contain L1, L2, and L3 caches to provide as much data as close to the CPU as possible. Storing as much data in the cache as possible prevents stalling the ALU and, therefore maximizes the CPUs productivity. The L1-Cache is the fastest and smallest one, containing a few kilobytes, whereas the L3 cache is the biggest but also the slowest one. On modern CPUs, this corresponds to 32KB L1 Cache, 2MB L2 Cache, and another 24MB L3 Cache across all the P-cores (Intel 13700). Factually, it is 3MB if all the cores do some heavy lifting, but in many single-threaded cases, the other cores are not doing much work, and the L3 cache can be shared efficiently. Modern CPUs implement various methods to predict which data should be on which cache level — this mechanism is called cache prefetching and can preload data preemptively to increase a CPU&#39;s computing efficiency.</p><p>Second, to understand how our data is stored in memory, we remember that our 2D squared array is represented as a flattened 1D array. In all 6 cases, the array must be looped over for each row or column element. The row consists of consecutive memory <em>buckets</em>, also known as a stride. Column access does not touch consecutive buckets and can’t be loaded as a stride at once due to our row representation.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*aie3TsI9EsdlqTq0U34Xhw.png" /><figcaption>Row Access vs Column Access</figcaption></figure><p>The difference might look neglectable at first hand, but by diving deeper into the CPU architecture — it is significant. Moving data within the CPU from one cache level to another (or memory) does not happen for individual elements but for a bunch of them called a line. A modern processor&#39;s average cache line size is 64 Bytes (Intel).<br>Moving a line from one cache level to another means that 64 Bytes are transferred simultaneously. Standard Java Float data types represent each matrix element — taking up 4 Bytes. Consequently, ideally, 16 elements can be transferred simultaneously. This results in a ratio of 1/16 loads per element when moving a row of an array. (A load of 16 elements can be done every 16 elements of the most inner loop, when accessing the matrix row per row.)</p><p>Consequently, as mentioned above, we can categorize the six implementations into three groups based on their access patterns, visualize them, and make runtime assumptions. For all the further elaborations, we assume the matrix <em>size</em> is very large, and we can approximate 1/<em>size</em> as 0. (By making this assumption, row ends do not interfere with the loading pattern because they are neglectable compared to the number of items in each row.)</p><p><strong>Type IJK, JIK:</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*5ZuytlgHd88jJbrVRGRhgQ.png" /></figure><p>Both variants use the following inner loop in code:</p><pre>...<br>float sum = 0.0f;<br>for (int k = 0; k &lt; n; k++) {<br>    sum += a[i * n + k] * b[k * n + j];<br>}<br>result[i * n + j] = sum;<br>...</pre><p>Based on the code, the sum doesn’t need to be written back into the array C until the most inner loop is finished. Therefore, the cache does not need to be accessed (0) for the write-back of matrix C. Looping over array B results in a vertical access pattern, leading to unfortunate access every cycle. No stride can be loaded, so data handling is done in every loop (1). Matrix A can benefit from the row stride where only once every 16 elements, one line has to be loaded, resulting in an access pattern of (1/16).</p><p>Summarizing:</p><ul><li>Matrix A: 1/16</li><li>Matrix B: 1.0</li><li>Matrix C (Result): 0</li></ul><p>Total memory access per element in this pattern: <strong>1.0625</strong></p><p><strong>Type KIJ, IKJ:</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*mLvgeUf3JnA5PgEu0Qh9YA.png" /></figure><p>The most inner loop is represented by:</p><pre>float aik = a[i * n + k];<br>for (int j = 0; j &lt; n; j++) {<br>    result[i * n + j] += aik * b[k * n + j];<br>}</pre><p>According to the previous methodology, matrix A is not accessed in the most inner loop, resulting in 0 cache access. Matrix B and C (result) can benefit from a stride in reading or writing. Therefore, matrices B and C (result) have very beneficial access patterns where only every 16 elements, a full line needs to be moved, resulting in 1/16 accesses per element for both matrices.</p><p>Summarizing:</p><ul><li>Matrix A: 0</li><li>Matrix B: 1/16</li><li>Matrix C (Result): 1/16</li></ul><p>Total memory access in this pattern: <strong>0.125</strong></p><p>We should anticipate that the current implementation should perform better than the first implementation due to the lower number of cache accesses per element!</p><p><strong>Type JKI, KJI:</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*pcKz9fPGyE0lvRohEEFNqg.png" /></figure><p>Same story as before, leading to the summary:</p><ul><li>Matrix A: 1</li><li>Matrix B: 0</li><li>Matrix C (Result): 1</li></ul><p>Total memory access in this pattern: <strong>2.0</strong></p><p>Most likely, storing the data comes with a write-back penalty, so it is not easy to answer which solution is the fastest, but we know that JKI, and KJI will probably be the slowest.</p><h4>Result</h4><p>The benchmark was run on a modern Intel platform without thermal throttling or Turbo Boost to maximize the computing stability as far as influenceable.<br>Instead of measuring milliseconds, CPU cycles were counted for each benchmark. This provides a better understanding of what is happening under the hood and is way more invariant to the frequency changes of the CPU. Further, it enables us to make conclusions based on the number of cycles per element used.</p><p>Remember that the most inner loop always contains a matrix multiplication and a sum operation: <em>sum += a[i * n + k] * b[k * n + j]. </em>Results with less than one cycle per element indicate that some SIMD / vector parallelism was used, and the JVM optimized the code — which is beneficial for runtime.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*NzNZMd9xM-cMlJHLi4mK8w.png" /></figure><h4>Discussion</h4><p>To the broadest extent, the results look like we expected them; there are three different groups, each containing two implementations. The discussion of whether we expected IJK &amp; JIK or KIJ &amp; IKJ to be the fastest can be left open. On one hand, cache-write back is anticipated with a write-back penalty. On the other hand, the vertical row pattern is so predictable that a modern CPU should be able to detect this as a stride and fetch the data preemptively.</p><p>We can observe that the JVM optimizes the code, and uses vector parallelism to do so. Vector parallelism is used in all implementations as the performance per element is lower than one regarding CPU cycles. A number below 1.0 means that more than one element can be processed within one CPU cycle, which is only feasible if multiple elements are processed simultaneously, manifesting the assumption that the JVM used vector parallelism to accelerate the job. This assumption is valid for the entire benchmark. Still, we see the effects of stalling and busy-waiting for data in larger array sizes due to some unfortunate memory access patterns in some implementations.</p><p>Surprisingly, throughput per element stays constant even at huge array sizes (2048 x 2048) for the two implementations with the least cache access. Previously, it was necessary to partition the matrix into blocks to optimize for more cache locality and less cache access. (I reran the benchmark several times, resulting in the same runtime!) It is fair to assume that the prefetching works reasonably well because the access pattern is almost ideal, and modern CPUs have huge cache sizes. In the 20 years between 1997 (Pentium 2) and 2017 (Cascade Lake), cache sizes for L1 and L2 doubled, which is neglectable to the 10x clock speed improvement during this time. Nevertheless, cache access times were reduced by around 50%, resulting in more efficient loading. These factors may account for the absence of busy-wait and ALU starvation in the two (IKJ, KIJ) implementations at huge matrix sizes.</p><p>At this point, spending more time investigating the cache loading effects is not justifiable as the Strassen-Algorithm is a far better-performing implementation of simple matrix multiplications and should be used instead of this one. <em>Christoph, my trusty proofreader, would love to see a Strassen benchmark — if you agree, please comment below, and I might look into it! :)</em><br>Nevertheless, it is interesting to see which effects happen when investigating a simple algorithm like this.</p><h4>Conclusion</h4><p>The most important takeaway is that although we live in a world with high-level languages, the underlying hardware and its properties can not be neglected. No matter the language, algorithms can still be optimized for cache locality, and performance uplifts can be seen in the following:</p><ul><li><strong>Data structure organization:</strong> Use strides for 2D matrix representation by transforming it to a 1D structure in memory. (Java and C# differ here because of the ability to create multidimensional arrays [x,y] in C#).</li><li><strong>Data Access Patterns: </strong>Refactor loops so that less data needs to be moved around and more is available to keep the ALU busy.</li></ul><p>We should know now that our system can benefit from <em>Cache Friendly Code</em>.</p><h4>Acknowledgment</h4><ul><li><a href="https://www.linkedin.com/in/camrein/">Christoph Amrein</a>, fixing some paragraphs and improving readability.</li></ul><h4>References</h4><ul><li><a href="http://cpudb.stanford.edu/">http://cpudb.stanford.edu/</a></li><li><a href="https://en.wikichip.org/wiki/intel/core_i7/i7-13700k">https://en.wikichip.org/wiki/intel/core_i7/i7-13700k</a></li><li><a href="https://learn.microsoft.com/en-us/dotnet/fundamentals/code-analysis/quality-rules/ca1814#example">https://learn.microsoft.com/en-us/dotnet/fundamentals/code-analysis/quality-rules/ca1814#example</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=859111845c25" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Observing Java 19 JVM optimization with JMH + hsdis + PerfASM: Holy trinity of low-level…]]></title>
            <link>https://medium.com/@Styp/observing-java-19-jvm-optimization-with-jmh-hsdis-perfasm-holy-trinity-of-low-level-9bd1daecf1b3?source=rss-3ab3e769942e------2</link>
            <guid isPermaLink="false">https://medium.com/p/9bd1daecf1b3</guid>
            <category><![CDATA[java19]]></category>
            <category><![CDATA[jvm]]></category>
            <category><![CDATA[jmh]]></category>
            <category><![CDATA[perf]]></category>
            <category><![CDATA[java]]></category>
            <dc:creator><![CDATA[Martin Stypinski]]></dc:creator>
            <pubDate>Tue, 08 Aug 2023 15:00:36 GMT</pubDate>
            <atom:updated>2023-08-08T15:00:36.863Z</atom:updated>
            <content:encoded><![CDATA[<h3>Observing Java 19 JVM optimization with JMH + hsdis + PerfASM: Holy trinity of low-level benchmarking — Part II</h3><p>The <a href="https://medium.com/@Styp/observing-java-19-jvm-optimization-with-jmh-hsdis-perfasm-part-i-e80c4907e2f9">previous article</a> of this mini-series focused on assembly code generation using the hsdis library to intercept the Java JIT emitted output. In this piece, we continue to dive deeper into the execution platform, the physical CPU, where the code runs.</p><h3>Motivation</h3><p>This article aims to show how to use JMH with Perf. In order to provide more than an installation guideline, we will dive into two versions of matrix multiplication and their implications on runtime. The algorithms of choice are a simple baseline algorithm and a cache-optimized version. Cache congestion is easily detectable with Perf and is a good starting point to explain the tool.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*BD97tV8V1kv3QHkZ6PIrgQ.png" /></figure><h3>Installation</h3><p>The installation of Perf is straightforward on any Linux machine. In this case, a Ubuntu 22.04 LTS was used, and the Perf-Tool suite can be installed through the package manager.</p><pre>sudo apt install linux-kernel-tools</pre><p>Perf is a tool to monitor, amongst others, hardware and software events, such as cache loads, branching, or page faults triggered by the OS. By default, Perf uses an <em>event level</em> of 4 which is fine for any system as it is not too invasive on the host. Therefore, only a minority of all important events can be detected by Perf. We need to get as much information as possible for development purposes by sacrificing security considerations. Consequently, we want to set the ‘<em>perf_event_paranoia</em>’ to -1:</p><pre>sudo /etc/sysctl.d/perf.conf &gt; kernel.perf_event_paranoid = -1</pre><p>The easiest way is to set the parameter during OS startup. During a normal start, all files in the ‘<em>/etc/sysctl.d/’</em> folder are evaluated, and Perfs’ ‘<em>perf_event_paranoia</em>’ can be set for good. (The default config will be used once again by deleting the file.)</p><h3>Methods</h3><p>The selected algorithm is matrix multiplication, well suited to benchmark computational throughput. The amount of computation is reasonably high compared to the amount of memory reads and writes. A simple implementation runs in O(n^3) time complexity and involves much computation while maintaining a reasonably low amount of memory access.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*BCaiSYyH09v7m-peJoVfCw.png" /><figcaption>High computational intensity, low memory intensity</figcaption></figure><p>With growing matrix sizes, memory access will become an area worth optimizing. Large row or column items contain enough floating point numbers to exhaust the CPUs L1 cache. Subsequently, it is the perfect example to investigate cache congestion on the larger matrix multiplications.</p><h4>Baseline</h4><p>The baseline case is the simplest algorithm implementation and is typical homework for a Programming 101 class. The algorithm takes each row and column vector and multiplies it. In this example, the only difference is that the matrix is represented as a single-dimensional array. Consequently, the next column entry (A[0,0] -&gt; A[0,1]) of the matrix is at position <em>i-&gt;i+1</em>, whereas the next row entry (A[0,0] -&gt; A[1,0]) of the matrix can be found at <em>i-&gt;i+matrix_width</em>. Resulting in the following code form: <em>A[x][y] =&gt; V[x*matrix_width+y]</em> (for zero-indexed arrays).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*x0Q_Tw11TTnVimKhQMJmvw.png" /><figcaption>2D matrix represented in a 1D array</figcaption></figure><p>Flattening a 2D array into a 1D array works well for squared arrays. Any further deep dives and reasons for doing so are avoided to keep the main story of the article.</p><pre>public float[] baseline(float[] a, float[] b, int n) {<br>    float[] c = new float[n * n];<br><br>    for (int i = 0; i &lt; n; i++) {<br>        for (int j = 0; j &lt; n; j++) {<br>            float sum = 0.0f;<br>            for (int k = 0; k &lt; n; k++) {<br>                sum += a[i * n + k] * b[k * n + j];<br>            }<br>            c[i * n + j] = sum;<br>        }<br>    }<br>    return c;<br>}</pre><p><strong>Blocked</strong></p><p>This simple algorithm works well, especially for small matrix sizes. Its limitation is that growing the matrix makes each row and column longer and can exhaust the CPU’s fast L1 cache and degrade performance.</p><p>The hypothesis is that by implementing the algorithm in a <em>blocked</em> way, the CPU can use more cache local data and therefore avoid latency through RAM access penalties. Data stored in cache is <em>immediately</em> accessible, while accessing data in memory takes time. Therefore, the blocked algorithm tries to exploit as much cache local data as possible and to reduce the amount of memory round trips to improve overall performance.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*spDGwFX-9LWMmxbmJi4g0g.png" /><figcaption>Cache miss is expensive; we better avoid it!</figcaption></figure><p>The term blocked refers to slicing the array up into sub-areas, where data can be kept fairly close to the ALU (Arithmetic Logical Unit), and by computing sub-area by sub-area, the performance should improve by increasing cache-locality and decreasing random memory access.</p><p>An optimal block size can be determined by benchmarking the algorithm and depends on cache size and CPU architecture. In this case, a Xeon Gold 6212U was used with fairly big cache sizes compared to some desktop counterparts. The blocksize yielding the best results was <em>16</em>. Consequently, the smallest matrix width to run is 16, as a smaller size can not be handled by the provided implementation. Another limitation is that only multiples of the block size can be computed. Still, this limitation improves code readability and is carefully chosen to prove the point.</p><pre>public float[] blocked(float[] a, float[] b, int n, final int blocksize) {<br>    float[] c = new float[n * n];<br><br>    for (int kk = 0; kk &lt; n; kk += blocksize) {<br>        for (int jj = 0; jj &lt; n; jj += blocksize) {<br>            for (int i = 0; i &lt; n; i++) {<br>                for (int j = jj; j &lt; jj + blocksize; ++j) {<br>                    float sum = c[i * n + j];<br>                    for (int k = kk; k &lt; kk + blocksize; ++k) {<br>                        sum += a[i * n + k] * b[k * n + j];<br>                    }<br>                    c[i * n + j] = sum;<br>                }<br>            }<br>        }<br>    }<br>    return c;<br>}</pre><h4>Setup</h4><p>The setup is a normal JMH + Java Gradle project with runtime parameters for perf. Accordingly, a sample config could look like this:<br>(This depends on setup and goal of profiling, so your preferences might be different.)</p><pre>jmh {<br>    iterations = 5 // Number of measurement iterations to do.<br>    benchmarkMode = [&#39;sample&#39;] // Benchmark mode. Available modes are: [Throughput/thrpt, AverageTime/avgt, SampleTime/sample, SingleShotTime/ss, All/all]<br>    batchSize = 1 // Batch size: number of benchmark method calls per operation. (some benchmark modes can ignore this setting)<br>    fork = 1 // How many times to forks a single benchmark. Use 0 to disable forking altogether<br>    failOnError = true // Should JMH fail immediately if any benchmark had experienced the unrecoverable error?<br>    forceGC = false // Should JMH force GC between iterations?<br>    jvm = &quot;/usr/bin/java&quot;<br>    humanOutputFile = project.file(&quot;${project.buildDir}/reports/jmh/human.txt&quot;) // human-readable output file<br>    resultsFile = project.file(&quot;${project.buildDir}/reports/jmh/results.txt&quot;) // results file<br>    operationsPerInvocation = 10 // Operations per invocation.<br>    <br>    // perf profiler needs to be setup here:<br>    profilers = [&#39;perfnorm:events=L1-dcache-loads,LLC-loads,LLC-load-misses,L2_RQSTS.ALL_DEMAND_DATA_RD,CYCLE_ACTIVITY.STALLS_TOTAL,CYCLE_ACTIVITY.STALLS_L1D_MISS,CYCLE_ACTIVITY.STALLS_L2_MISS,CYCLE_ACTIVITY.STALLS_L3_MISS,CYCLE_ACTIVITY.CYCLES_L1D_MISS,CYCLE_ACTIVITY.CYCLES_L2_MISS,CYCLE_ACTIVITY.CYCLES_L3_MISS&#39;] // Use profilers to collect additional data. Supported profilers: [cl, comp, gc, stack, perf, perfnorm, perfasm, xperf, xperfasm, hs_cl, hs_comp, hs_gc, hs_rt, hs_thr, async]<br>    <br>    timeOnIteration = &#39;30s&#39; // Time to spend at each measurement iteration.<br>    resultFormat = &#39;CSV&#39; // Result format type (one of CSV, JSON, NONE, SCSV, TEXT)<br>    synchronizeIterations = false // Synchronize iterations?<br>    timeUnit = &#39;ns&#39; // Output time unit. Available time units are: [m, s, ms, us, ns].<br>    verbosity = &#39;NORMAL&#39; // Verbosity mode. Available modes are: [SILENT, NORMAL, EXTRA]<br>    warmup = &#39;1s&#39; // Time to spend at each warmup iteration.<br>    warmupBatchSize = 10 // Warmup batch size: number of benchmark method calls per operation.<br>    warmupForks = 0 // How many warmup forks to make for a single benchmark. 0 to disable warmup forks.<br>    warmupIterations = 1 // Number of warmup iterations to do.<br>    warmupMode = &#39;INDI&#39; // Warmup mode for warming up selected benchmarks. Warmup modes are: [INDI, BULK, BULK_INDI].<br>    warmupBenchmarks = [&#39;.*Warmup&#39;] // Warmup benchmarks to include in the run in addition to already selected. JMH will not measure these benchmarks, but only use them for the warmup.<br>    zip64 = true // Use ZIP64 format for bigger archives<br>    jmhVersion = &#39;1.29&#39; // Specifies JMH version<br>    includeTests = false // Allows to include test sources into generate JMH jar, i.e. use it when benchmarks depend on the test classes.<br>    duplicateClassesStrategy = DuplicatesStrategy.EXCLUDE // Strategy to apply when encountring duplicate classes during creation of the fat jar (i.e. while executing jmhJar task)<br>}</pre><h3>Results</h3><p>The raw output of the benchmarks should look similar to the following table; again, as machines are different and hardware is different, the output will look different!</p><pre>Benchmark                       size  Mode Cnt        Score        Units<br>------------------------------------------------------------------------<br>mmBaseline                        32  avgt   5     4633.607        ns/op<br>mmBaseline:CPI                    32  avgt            0.250    clks/insn<br>mmBaseline:IPC                    32  avgt            4.004    insns/clk<br>mmBaseline:L1-dcache-load-misses  32  avgt            7.738         #/op<br>mmBaseline:L1-dcache-loads        32  avgt        16674.312         #/op<br>mmBaseline:L1-dcache-stores       32  avgt          435.131         #/op<br>mmBaseline:L1-icache-load-misses  32  avgt            0.996         #/op<br>mmBaseline:LLC-load-misses        32  avgt            0.035         #/op<br>mmBaseline:LLC-loads              32  avgt            0.081         #/op<br>mmBaseline:LLC-store-misses       32  avgt            3.760         #/op<br>mmBaseline:LLC-stores             32  avgt            3.910         #/op<br>mmBaseline:branch-misses          32  avgt            3.522         #/op<br>mmBaseline:branches               32  avgt         4962.787         #/op<br>mmBaseline:cycles                 32  avgt        14377.633         #/op<br>mmBaseline:dTLB-load-misses       32  avgt            0.140         #/op<br>mmBaseline:dTLB-loads             32  avgt        16575.955         #/op<br>mmBaseline:dTLB-store-misses      32  avgt            0.071         #/op<br>mmBaseline:dTLB-stores            32  avgt          433.736         #/op<br>mmBaseline:iTLB-load-misses       32  avgt            0.014         #/op<br>mmBaseline:iTLB-loads             32  avgt            0.006         #/op<br>mmBaseline:instructions           32  avgt        57568.506         #/op</pre><p>The output is according to the <em>profile</em> parameters in the JMH start-up settings.</p><p>By aggregating the most important metrics and visualizing the data, we can have a deeper look at the cache access differences between both algorithms.</p><p>The first plots show strictly the data aggregated in terms of runtimes. The first sub-plot shows the runtime performance in terms of overall speed compared to array size — on a logarithmic scale. The second-sub plot shows the runtime per operation or element. The third sub-plot illustrates the speed-up quantifying a performance up-lift,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/994/1*kXEKkOPeJ5aFnI96viPrdw.png" /><figcaption>Runtime benchmarks on the simple and blocked matrix multiplication algorithm.</figcaption></figure><p>The second group of plots focuses on cache access, mainly L1 cache, and the resulting performance. The squared matrix size was incrementally increased from 16 to 2048 row and column width, always by a power of 2 (2⁵ — 2¹¹). (The size 16, the smallest size, is an implementation limitation of the blocked algorithm.) The second sub-plot shows the L1 cache access per element compared to L2, L3, and Ram access. The last sub-plot shows the ratio of L1-Cache access in proportion to all the other data lookups.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/1*tENoxf3Nl3zyMyeyfnTbpw.png" /><figcaption>Deep dive into the caches of both algorithms.</figcaption></figure><h3>Discussion</h3><p>So apart from learning how to install and use perf in a Java JMH Setup, the question remains: <em>What did we learn from this experiment?</em></p><p>First of all, the results show that the simple implementation has a hypothetical lower-bound of O(n^3), as expected. Cache congestion and latency penalties start to occur at a matrix width of 2⁸ to 2⁹. At this point, data needs to be loaded from L2, L3, or RAM. This increases latency noticeably and decreases computational throughput by stalling the ALU (Busy Wait), ultimately leading to performance degradation.<br><em>(Actually, it does not stall the ALU on modern processors, but Hyper-Threading or SMT kicks in; it changes the data flow through the ALU onto another pipeline. For processors without HT, an ALU stall can occur. In the given case, the task gets stalled due to unavailable data.).</em></p><p>Further diving into the RAW data shows a spike in L3-Cache access on matrix sizes above a width of 512 (2⁹). It is no coincidence that performance degradation can be measured by almost a factor of two at this point. The results were gathered on an Intel Cascade Lake (Skylake+) platform. Intels documents reveal that an L1D-cache load into a register needs 4 cycles, the best-case L2 cache load needs 12 cycles, and the best-case L3 cache load needs 44 cycles. (Further reading in the resource section.) <br>Loading data from the slower L3-Cache takes 11 times more time than loading data from the L1-Cache, so it better be there! These numbers also explain why the higher L1-Cache access ratio dramatically improves the blocked algorithms&#39; performance! Yes, cache-locality is still an important area of optimization for high-performing algorithms!</p><p>To conclude, not only have we established a meaningful toolkit with Java JMH + hsdis.so + Perf to investigate low-level JVM code generation, but we can also understand the results and the consequences.</p><h3>Conclusion</h3><p>Although Java is run on the Java Virtual Machine and the Just-in-Time compiler is responsible for emitting the platform&#39;s correct assembly code, the same rules apply as for compiled languages. Cache misses are still very expensive and should be avoided if performance is the most important aspect of a particular algorithmic implementation.</p><p>Although not entirely written as a tutorial, this article should provide developers who need to look under the JVM hood with a toolbox to debug and profile certain effects. This is not a toolkit for daily driving but for these cases where algorithms must be optimized for the utmost performance. It can also be used to understand what is happening on the hardware level of a particular piece of code.</p><h3>Acknowledgment</h3><ul><li><a href="https://www.linkedin.com/in/camrein/"><strong>Christoph Amrein</strong></a><strong>:</strong> For rearranging some pieces, adding background information, and improving the overall post quality.</li><li><a href="https://www.linkedin.com/in/marc-juchli/"><strong>Marc Juchli</strong></a><strong>:</strong> For his valuable input in improving the readability and fixing some coherency issues.</li><li><a href="https://www.linkedin.com/in/kirusanth-poopalasingam-0685bb1a1/"><strong>Kirusanth Poopalasingam:</strong></a> For his valuable input in some key passages of the blog post.</li></ul><h3>Resources:</h3><ul><li><a href="https://en.wikichip.org/wiki/intel/microarchitectures/skylake_(client)">https://en.wikichip.org/wiki/intel/microarchitectures/skylake_(client)</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9bd1daecf1b3" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Observing Java 19  JVM optimization with JMH + hsdis + PerfASM — Part I]]></title>
            <link>https://medium.com/@Styp/observing-java-19-jvm-optimization-with-jmh-hsdis-perfasm-part-i-e80c4907e2f9?source=rss-3ab3e769942e------2</link>
            <guid isPermaLink="false">https://medium.com/p/e80c4907e2f9</guid>
            <category><![CDATA[jvm]]></category>
            <category><![CDATA[java-benchmarking]]></category>
            <category><![CDATA[benchmarking]]></category>
            <category><![CDATA[java]]></category>
            <category><![CDATA[java19]]></category>
            <dc:creator><![CDATA[Martin Stypinski]]></dc:creator>
            <pubDate>Wed, 05 Apr 2023 15:55:52 GMT</pubDate>
            <atom:updated>2023-04-05T15:55:52.823Z</atom:updated>
            <content:encoded><![CDATA[<h3>Observing Java 19 JVM optimization with JMH + hsdis + PerfASM: Holy trinity of low-level benchmarking — Part I</h3><p>This article focuses on installing and using the hsdis library as a decompiler for the JVMs emitted code.</p><h3>Motivation</h3><p>While investigating Java Vector API, it became necessary to understand the generated code to verify specific hypotheses. Unfortunately, the path of sophisticated benchmarking led to a very rocky but successful road:</p><ul><li>JMH — Java Microbenchmarking Harness: A framework broadly used to benchmark Java methods in an atomic and capsulated way.</li><li>Hsdis.so: Hsdis is a disassembler library to make JVM-generated human-readable ASM code.</li><li>PerfASM: Linux Perf started as a tool to tap into the CPUs performance counters, such as cache miss, branch mispredict, etc. <em>(Covered in part 2).</em></li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*0cNMdLo9LiP7AH2TJ482IA.png" /></figure><p>By using these three frameworks, it is possible to use method runtimes as a benchmark and tap into the underlying generated code. The code can help to understand which optimizations have been applied and which areas of the underlying hardware have been utilized.</p><p>The necessity for such a toolchain might sound very useless and niche, but it is mighty to understand how the Just-in-Time compiler (JIT) works. Further, it is possible to optimize algorithms based on their hardware-level limitations.</p><h3>Installation</h3><p>The toolkit works on any modern operating system as long as no virtualization layer abstracts the hardware. Virtualized environments have limitations in passing the CPUs performance counter to the Perf toolkit. When benchmarking, the results depend on the platform and can show different results based on cache size, micro-architecture, or CPU generation.</p><p>This installation guide was written on an Ubuntu 22.04 LTS system with the target of Java 19 and should be reproducible accordingly. (Java 18 and 20 should be similar). Likewise, it should work on OSX and Windows if the OS runs on real hardware, but installation and dependencies will differ.</p><h4><strong>Hsdis Installation</strong></h4><p>The HotSpot-Disassembler <em>hsdis</em> is a plugin for the HotSpot JVM compiler, which disassembles JIT-compiled native code back into mnemonic-based and human-readable assembly language. By default, Java is not shipped with any hsdis library and needs to be compiled to a specific target micro-architecture. In this case, OpenJDK 19 was used:</p><ol><li>Check the Java version you want to use <em>hsdis</em> with and clone the matching GitHub repo.</li></ol><pre>git clone https://github.com/openjdk/jdk<br>git checkout jdk-19+36</pre><p>2. Download binutils-2.38: <a href="https://ftp.gnu.org/gnu/binutils/">https://ftp.gnu.org/gnu/binutils/</a><br>It is important to stick to <em>binutils-2.38</em>, there is a major API change in 2.39+, and there is still an ongoing PR at this point: <br><a href="https://github.com/openjdk/jdk/pull/10817">https://github.com/openjdk/jdk/pull/10817</a></p><pre>wget https://ftp.gnu.org/gnu/binutils/binutils-2.38.tar.gz</pre><p>3. Some dependencies might be needed; the exact setup might vary depending on the installation of the machine.</p><pre>apt-get install build-essential<br>apt-get install libasound2-dev<br>apt-get install libcups2-dev<br>apt-get install libfontconfig1-dev<br>apt-get install libx11-dev libxext-dev libxrender-dev libxrandr-dev libxtst-dev libxt-dev</pre><p>4. Make hsdis-amd64.so:</p><pre>sh ./configure - with-hsdis=binutils - with-binutils-src=~/binutils-2.38/<br>make clean build-hsdis</pre><p>5. The build file needs to be copied to the correct location:</p><pre>.../build/linux-x86_64-server-release/support/hsdis<br>hsdis-amd64.so</pre><h3>Method</h3><p>Once the installation is completed, it is time to figure out if everything works as expected. The following code should be enough to test the assembly code generation through the JIT compilers:</p><pre>package ch.styp;<br><br>import java.util.Random;<br><br>public class TestHsdis {<br><br>    public static void main(String... args) {<br>        TestHsdis testHsdis = new TestHsdis();<br>        var size = 2048;<br>        var left = initFloatArray(size);<br>        var right = initFloatArray(size);<br><br>        for(int i = 0; i &lt;= 10_000; i++) {<br>            var result = testHsdis.addArrays(left, right);<br>        }<br>    }<br><br>    public static float[] initFloatArray(int length){<br>        var floatArray = new float[length];<br><br>        Random rand = new Random();<br>        for(var i = 0; i&lt;length; i++){<br>            floatArray[i] = rand.nextFloat();<br>        }<br>        return floatArray;<br>    }<br><br>    private float[] addArrays(float[] left, float[] right) {<br>       float[] result = new float[left.length];<br>        for(int i=0; i &lt; left.length; i++){<br>           result[i] = left[i] + right[i];<br>       }<br>        return result;<br>    }<br><br>}</pre><p>The area to investigate in the provided code snipped is the addArrays method which the JIT compilers should optimize.</p><p>The method gets invoked 10&#39;000 times to trigger the C2 compiler. Java has two sets of JIT compilers: The C1 and the C2 compiler; the first was designed to run fast and is needed where only a few method invocations are used, whereas the second is used where a little more compile time doesn’t hurt. Compile time is fine if many invocations occur, and a shortened per-invocation runtime can offset the optimization overhead of the JIT compiler.</p><pre>|    | Calls  |<br>|----|--------|<br>| C1 |  1&#39;500 |<br>| C2 | 10&#39;000 |<br>|----|--------|</pre><p>According to the Oracle documentation (check resource section), the table shows which JIT compiler is used and the needed method calls count. Using the C2 compiler can be enforced by setting the invocation number to greater than 10&#39;000. Therefore the demo code had to be looped accordingly often.</p><p>To unlock the diagnostic options and thereby generate the assembly code, the following compiler flags need to be added:</p><pre>javac ch/styp/Test<br>java -XX:+UnlockDiagnosticVMOptions \<br>     -XX:+PrintAssembly \<br>     -Xlog:class+load=info \<br>     -XX:+LogCompilation  ch/styp/TestHsdis &gt; test.txt</pre><p>The Java JVM accepts options by passing <em>-:X</em> or <em>-:XX</em> (experimental) to the command line arguments. Features can be activated by adding a (<em>+</em>) sign to the requested feature and deactivated by adding a (-) sign accordingly. These options are also handy in forcing the JVM to perform specific optimizations or suppressing them. Unfortunately, the documentation (check resource section) is not on par with the feature set, and there is no resource covering all the current features.</p><h3>Results</h3><p>The generated assembly code can be confusing at first. Finding the right passage is difficult, but the Java line number can often indicate where to important part lies. In this case, the output file was over 3000 lines of assembly code and the most relevant couple of lines:</p><pre>  0x00007f5c3c7b5dd3:   mov    0x18(%rsp),%r10<br>  0x00007f5c3c7b5dd8:   vmovdqu 0x10(%r10,%r8,4),%ymm0<br>  0x00007f5c3c7b5ddf:   mov    0x8(%rsp),%r10<br>  0x00007f5c3c7b5de4:   vaddps 0x10(%r10,%r8,4),%ymm0,%ymm0<br>  0x00007f5c3c7b5deb:   vmovdqu %ymm0,0x10(%rcx,%r8,4)<br>  0x00007f5c3c7b5df2:   mov    0x18(%rsp),%r10<br>  0x00007f5c3c7b5df7:   vmovdqu 0x30(%r10,%r8,4),%ymm0<br>  0x00007f5c3c7b5dfe:   mov    0x8(%rsp),%r10<br>  0x00007f5c3c7b5e03:   vaddps 0x30(%r10,%r8,4),%ymm0,%ymm0<br>  0x00007f5c3c7b5e0a:   vmovdqu %ymm0,0x30(%rcx,%r8,4)<br>  0x00007f5c3c7b5e11:   mov    0x18(%rsp),%r10<br>  0x00007f5c3c7b5e16:   vmovdqu 0x50(%r10,%r8,4),%ymm0<br>  0x00007f5c3c7b5e1d:   mov    0x8(%rsp),%r10<br>  0x00007f5c3c7b5e22:   vaddps 0x50(%r10,%r8,4),%ymm0,%ymm0<br>  0x00007f5c3c7b5e29:   vmovdqu %ymm0,0x50(%rcx,%r8,4)<br>  0x00007f5c3c7b5e30:   mov    0x18(%rsp),%r10<br>  0x00007f5c3c7b5e35:   vmovdqu 0x70(%r10,%r8,4),%ymm0<br>  0x00007f5c3c7b5e3c:   mov    0x8(%rsp),%r10<br>  0x00007f5c3c7b5e41:   vaddps 0x70(%r10,%r8,4),%ymm0,%ymm0<br>  0x00007f5c3c7b5e48:   vmovdqu %ymm0,0x70(%rcx,%r8,4)      ;*fastore {reexecute=0 rethrow=0 return_oop=0}<br>                                                            ; - ch.styp.TestHsdis::addArrays@27 (line 31)<br>                                                            ; - ch.styp.TestHsdis::main@37 (line 14)<br>  0x00007f5c3c7b5e4f:   add    $0x20,%r8d                   ;*iinc {reexecute=0 rethrow=0 return_oop=0}<br>                                                            ; - ch.styp.TestHsdis::addArrays@28 (line 30)<br>                                                            ; - ch.styp.TestHsdis::main@37 (line 14)<br>                                                            ;   {no_reloc}<br>  0x00007f5c3c7b5e53:   cmp    %r9d,%r8d<br>  0x00007f5c3c7b5e56:   jl     0x00007f5c3c7b5dd3           ;*goto {reexecute=0 rethrow=0 return_oop=0}</pre><p>Don’t worry; a more detailed explanation will follow. The code will be dissected in the discussion section to show which optimization methods the JVM applied to the provided code sample.</p><p><strong>Pro-Tip:</strong> Often, it is enough to search for “C2-” in the output. The area of interest is C2 optimized, as enforced in the example. This trick often helps to get into the ballpark of the line number where the magic is happening.</p><h3>Discussion</h3><p>So what did we learn apart from how to install hsdis for Java 19? A lot!</p><p>By looking closer into the code, we can already spot two optimization efforts that the JIT is applying to optimize the snipped.</p><h4>Auto-vectorization</h4><p>For anyone who has read the <a href="https://medium.com/@Styp/java-18-vector-api-do-we-get-free-speed-up-c4510eda50d2">previous post</a>, the term Auto-Vectorisation shouldn’t be something new or unknown. For the ones starting on this topic: Vectorisation on the CPU level is the ability to process multiple operations simultaneously, but only if all the operations are the same. In the provided case, vectorization is possible, consisting of applying a plus operator on two arrays. Instead of adding each array position after the other, the optimization technique can take a bunch of indices and add them at once. The operator that needs to be applied is always the same (+). SIMD parallelism (Vectorisation) is a CPU feature and varies depending on the platform.</p><p>The assembly code reveals how the code ran on the CPU:</p><pre>0x00007f5c3c7b5de4:   vaddps 0x10(%r10,%r8,4),%ymm0,%ymm0</pre><p>The mnemonic <em>vaddps</em> is translated to ‘Vectorized Add Packed Single-Precision Floating-Point’, indicating the CPU leveraged vector accelerated extensions.</p><pre>0x00007f5c3c7b5de4:   vaddps 0x10(%r10,%r8,4),%ymm0,%ymm0<br>...<br>0x00007f5c3c7b5e03:   vaddps 0x30(%r10,%r8,4),%ymm0,%ymm0</pre><p>Further, the distance between these two memory addresses is 0x20. The number indicates the memory offset, which is 32 Bytes in this case. Assuming that a standard Java Float type consists of 4 bytes per Float, eight numbers had to be processed in the CPU at once. The Intel assembly guide confirms this and indicates that the <em>%ymm0</em> registers can hold up to 8 32-bit numbers (AVX). So it is proven that although the example is a simple sequential piece of code, the C2 compiler optimized it to leverage the AVX instruction set!</p><h4><strong>Loop Unrolling</strong></h4><p>Loop unrolling is a technique to optimize the code to use fewer instructions to complete the same code sequence. The key idea is to reduce the compare and jump instructions and execute more “meaningful” operations in each loop.</p><p>The following code passage shows a piece of normal Java-Code:</p><pre>for (int x = 0; i &lt; 100; i++){<br>  do_something(i);<br>}</pre><p>By executing the program, the CPU executes the ‘do-something(x)’ part and will then have to increment the variable <em>i</em> by one and compare it with the branch condition <em>x &lt; 100. I</em>f the condition is <em>true</em>, the CPU must return to the top of the code. Translated to assembly code:</p><pre>add data (i) - (doing actual work)<br>add i +1(increment)<br>cmp (compare)<br>jl (jump to)</pre><p>The result is approximately 400 instructions that are emitted on the CPU to chew through this loop with 100 elements.</p><p>On the other hand, an unrolled loop contains multiple instructions in one loop and increments the counter by more than one. Translated to assembly:</p><pre>add data (0)<br>add data (1)<br>add data (2)<br>add data (3)<br>add i +4 (increment)<br>cmp (compare)<br>jl (jump to)</pre><p>The result is approximately 175 instructions for the 100 provided elements, as written in this example:</p><pre>for (int x = 0; i &lt; 100; i += 4){<br>  do_something(i + 0);<br>  do_something(i + 1);<br>  do_something(i + 2);<br>  do_something(i + 3);<br>}</pre><p>Although this compares apples and pears, the loop efficiency increases drastically. Consequently, the code runs faster. A downside is that the code needs more space as the assembly file contains a longer instruction sequence through loop-unrolling.</p><p><strong>Pro-Tip:</strong> you should not unroll your loops manually! The C1 and C2 compilers are so clever that they work on any target platform. Manual loop-unrolling might increase performance in some cases, but this is limited to edge cases and a highly platform-specific deployment.</p><h3>Conclusion</h3><p>To conclude this piece, the key takeaway should not only be the setup of hsdis.so to generate assembly code out of Java, but also an eye-opener to the JIT ability to optimize code. It is really interesting to see that a simple like this piece of code gets optimized by two already sophisticated optimizations; Auto-vectorisation and loop-unrolling.</p><p>I used this particular tool and method to investigate the low-level behavior for my previous blog post:</p><ul><li><a href="https://medium.com/@Styp/java-18-vector-api-do-we-get-free-speed-up-c4510eda50d2">Java 18: Vector API — Do we get free speed-up?</a></li><li><a href="https://medium.com/itnext/auto-vectorization-how-to-get-beaten-by-compiler-optimization-java-jit-vector-api-92c72b97fba3">Auto-vectorization: How to get beaten by compiler optimization — Java JIT &amp; Vector API!</a></li></ul><p>With all the clever optimizations in place, beating the JVMs C1 and C2 compilers is challenging as they are so well optimized and platform interoperable; the only possibility to outperform the JVM is in edge cases or on particular devices.</p><h3>Acknowledgment</h3><ul><li><a href="https://www.linkedin.com/in/marc-juchli/"><strong>Marc Juchli</strong></a><strong>:</strong> For his valuable input in improving the readability and fixing some coherency issues.</li><li><a href="https://www.linkedin.com/in/kirusanth-poopalasingam-0685bb1a1/"><strong>Kirusanth Poopalasingam:</strong></a> For his valuable input in some key passages of the blog post.</li></ul><h3>Resources</h3><ul><li><a href="https://www.oracle.com/java/technologies/javase/vmoptions-jsp.html">Java HotSpot VM</a></li><li><a href="https://www.infoq.com/articles/OpenJDK-HotSpot-What-the-JIT/">What the JIT!? Anatomy of the OpenJDK HotSpot VM</a></li></ul><p>Feel free to follow me for Part II where I will dive into the world of Perf and CPU level benchmarking. If you want to talk about it, please feel free to comment or contact me on <a href="https://www.linkedin.com/in/styp/">LinkedIn</a> directly.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e80c4907e2f9" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Auto-vectorization: How to get beaten by compiler optimization — Java JIT & Vector API!]]></title>
            <link>https://itnext.io/auto-vectorization-how-to-get-beaten-by-compiler-optimization-java-jit-vector-api-92c72b97fba3?source=rss-3ab3e769942e------2</link>
            <guid isPermaLink="false">https://medium.com/p/92c72b97fba3</guid>
            <category><![CDATA[java-18]]></category>
            <category><![CDATA[simd]]></category>
            <category><![CDATA[vector-api]]></category>
            <category><![CDATA[java]]></category>
            <dc:creator><![CDATA[Martin Stypinski]]></dc:creator>
            <pubDate>Wed, 20 Jul 2022 20:14:16 GMT</pubDate>
            <atom:updated>2022-12-14T13:32:14.026Z</atom:updated>
            <content:encoded><![CDATA[<h3>Auto-vectorization: How to get beaten by compiler optimization — Java JIT!</h3><h3>Motivation</h3><p>Recently, I investigated the new Vector API in its third iteration:<br><a href="https://medium.com/@Styp/java-18-vector-api-do-we-get-free-speed-up-c4510eda50d2">Java 18: Vector API — Do we get free speed up?!</a></p><p>This post is meant to follow up on some interesting findings that I couldn’t answer in the first post. I would like to summarise my findings and show how Java Vector API can accelerate code by leveraging platform intrinsics. The results for the fused-multiply-add (FMA) benchmark were somehow expected and showed promising results. However, the simple-sum example showed no improvement whatsoever. The average speed-up was 0%, and after running the benchmark repeatedly, it still showed 0% improvement. Now it is time to investigate this disappointment.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*rQwfov8n1Kk0oF3J1meWCQ.jpeg" /><figcaption>Illustration of me staring on the stellar 0x speed-up!</figcaption></figure><p>The simple sum is the most basic addition of two arrays <em>a</em> and <em>b</em>, resulting in an array <em>c</em>. We can also express this with the following lines of code:</p><pre>public static int[] simpleSum(int[] a, int[] b) {<br>    int c = new int[a.length];    <br>    for (var i = 0; i &lt; a.length; i++){<br>        c[i] = a[i] + b[i];<br>    }<br>    return c;<br>}</pre><p>The performance we obtained showed a 0x speed-up over all different array sizes, as visualized in this plot:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*89HbWUOFp9AmBHcUQfLdVA.png" /><figcaption>The benchmark and its tremendous 0% speed-up! Non-Vector representing the Java for-loop implementation, while Vector representing the native Vector API based implementation.</figcaption></figure><p>The benchmark was performed on an AVX-512 capable CPU with the widest register; therefore, the most significant runtime improvements for data-parallel instructions are expected. Nevertheless, it is fascinating that a pure java benchmark is on-par with the highly optimized solution.</p><h3>What is this just-in-time compilation (JIT) thing?</h3><p>At this point, we can assume that either our Vector API version is not working as expected or Java is applying some <em>acceleration magic</em> to certain critical areas of the code. However, to understand Java’s abilities to optimize the code, we need to look at the fundamental difference between Ahead-of-Time machine code generation and Just-in-Time machine code generation — as in Java.</p><p><strong>Ahead-of-Time machine code generation:</strong></p><p>Ahead-of-Time (AoT) machine code generation happens at compile time. This technique is used in languages such as C++. During the compilation process, the source code gets <em>transcribed</em> to machine code. Machine code depends on the target platform, such as x86, Itanium, ARM, M1. Consequently, the code is only <em>touched</em> during compile time and <em>transcribed</em> to the target platform’s assembly specification.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*2DmsjWH2UeqRAJiVPHlaHw.png" /><figcaption>Explaining the process of code compilation (E.g C++)</figcaption></figure><p><strong>Just-In-Time machine code generation:</strong></p><p>Au contraire, the Just-in-Time (JiT) machine code generation works a little more sophisticated. Instead of transcribing the code directly to a target platform’s assembly language, the code gets transcribed to an intermediate code known as Bytecode. The Java Bytecode is an intermediary representation covering the <em>JVMs instruction set </em>while incorporating some compiler optimizations.</p><p>The JIT compiler reads the Bytecode and emits the correct assembly instructions for the demanded platform (x86, ARM, etc.). Further, it can apply some more specific optimizations with the <em>knowledge</em> of the program flow.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*1fYQjaPgnnwtdAVegniAhA.png" /><figcaption>JVM-based languages with the two-stage compilation process.</figcaption></figure><p>The JIT compiler combines two approaches to machine code translation: Interpretation and Ahead-of-Time compilation. It is responsible for translating the Bytecode into the platform-specific instructions. With the added runtime knowledge, specific optimizations can be done, which are not evident at compile time. This can contribute to optimizing the code further and improve runtime performance over more traditional languages.</p><p><strong>It’s time to shine:</strong></p><p>With the understanding of the Just-in-Time compilers properties, one might ask what the benefit is compared to conventional Ahead-of-Time compilation. Let us explore this with a simple example:</p><pre>public void randomLoop(){<br>    var rnd = new Random();<br>    int maxItems = rnd.nextInt();<br>    for(int i = 0; i &lt; maxItems; i++){<br>        doSomethingWith(i);<br>    }<br>}</pre><p>An Ahead-of-Time compiler has no reasonable chance of knowing how many iterations the loop will execute. On the other hand, the Just-in-Time compiler knows precisely how big <em>maxItems</em> is — and can optimize for a <em>small</em>, <em>medium</em>, or <em>large</em> loop! (This snippet only shows the <em>knowledge</em> benefit during runtime, compared to Ahead-of-Time compilation. Of course, there is no guarantee for any Just-in-Time compiler improvements.)</p><h3><strong>Optimization Options</strong></h3><p><strong>Loop Unrolling:<br></strong>Loop unrolling is a optimization technique to minimize the loop overhead, such as boundary checking, variable increasing. Instead of checking the loop counter (i) and increasing it with every element, multiple elements are getting done in one loop-body in order to minimize overhead:</p><pre>public void normalLoop(){<br>    for(int i = 0; i &lt; 128; i++){<br>        doSomethingWith(i);<br>    }<br>}</pre><pre>public void unrolledLoop(){<br>    for(int i = 0; i &lt; 32; i+=4){<br>        doSomethingWith(i+0);<br>        doSomethingWith(i+1);<br>        doSomethingWith(i+2);<br>        doSomethingWith(i+3);<br>    }<br>}</pre><p>This is a prevalent technique used during Ahead-of-Time compilation, as long as the number of iterations is known. (Ever asked yourself why C++ <em>const variables </em>are so important — now you know it!) In Just-in-Time compiler is aware of the loop size on runtime and can therefore force a loop-unroll depending on the size of the variable.</p><p><strong>Vectorization:<br></strong>Another potential approach is automatic vectorization (Auto-vectorization). Vector-based instructions trigger the processors’ specific SIMD (Single instruction, multiple data) registers which can execute one operation on numerous elements during the same instruction cycle. The <em>simpleSum</em> code snipped is a perfect example that could be optimized with vectorization. With Javas Vector API, we can write platform-agnostic but SIMD-optimized code.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*1CReEwIob8gL4Kuouz7yyA.png" /><figcaption>Single Instruction, Single Data (SISD) — vs — Single Instruction, Multiple Data (SIMD)</figcaption></figure><p>This introduction leads to the open question: <strong>Why am I not getting any speed-up when comparing a primitive implementation with a Vector API accelerated implementation?</strong></p><h3>Finding the culprit: Auto Vectorisation or Loop Unrolling?</h3><p>We have now addressed two strategies to optimize simple loops with arithmetic operations. Finally, it is time to prove which JIT optimizations eradicate the potential speed-up of a manually tweaked code.</p><p>The JVM consists of various diagnostics flags that enable storing the emitted assembly code into a log file. Further, it is possible to turn on and off some JIT features. This enabling and disabling of JIT features facilitates an investigation of optimization techniques and their consequence on the code’s runtime. For example, with Auto-vectorization and Loop-unrolling turned off, it is possible to generate the most primitive assembly code for the simpleSum example:</p><pre><em>Operation: add a[i]+b[i] and move data to c[i]:</em><br>0x11dad89e0:   mov    0x10(%r8,%r13,<em>4</em>),%eax<br>0x11dad89e5:   add    0x10(%r11,%r13,<em>4</em>),%eax<br>0x11dad89ea:   mov    %eax,0x10(%rbx,%r13,<em>4</em>)       ;*iastore </pre><pre><em>Operation: Increment Loop-Counter i:</em>                                                         <em>ch.styp.TestMain</em>::addArray@<em>27</em> (line <em>37</em>)<br>0x11dad89ef:   inc    %r13d                        ;*iinc </pre><pre><em>Operation: Compare Loop-Counter i, and jump to add-Block:</em>                                                       <em>ch.styp.TestMain</em>::addArray@<em>28</em> (line <em>36</em>)<br>0x11dad89f2:   cmp    %r9d,%r13d<br>0x11dad89f5:   jl     0x11dad89e0                  ;*goto </pre><p>The next generated code snipped is the one with the turned on Loop-unrolling feature. Consequently, this configuration generates the following code:</p><pre><em>Operation: add a[i+0]+b[i+0] and move data to c[i+0]:<br></em>0x11bd3e240:   mov    0x10(%rbp,%rdi,<em>4</em>),%esi<br>0x11bd3e244:   add    0x10(%rdx,%rdi,<em>4</em>),%esi<br>0x11bd3e248:   mov    %esi,0x10(%r8,%rdi,<em>4</em>)</pre><pre><em>Operation: add a[i+1]+b[i+1] and move data to c[i+1]:</em><br>0x11bd3e24d:   mov    0x14(%rbp,%rdi,<em>4</em>),%r10d<br>0x11bd3e252:   add    0x14(%rdx,%rdi,<em>4</em>),%r10d<br>0x11bd3e257:   mov    %r10d,0x14(%r8,%rdi,<em>4</em>)</pre><pre><em>Operation: add a[i+2]+b[i+2] and move data to c[i+2]:<br></em>0x11bd3e25c:   mov    0x18(%rdx,%rdi,<em>4</em>),%r10d<br>0x11bd3e261:   add    0x18(%rbp,%rdi,<em>4</em>),%r10d<br>0x11bd3e266:   mov    %r10d,0x18(%r8,%rdi,<em>4</em>)</pre><pre><em>Operation: add a[i+3]+b[i+3] and move data to c[i+3]:<br></em>0x11bd3e26b:   mov    0x1c(%rdx,%rdi,<em>4</em>),%r10d<br>0x11bd3e270:   add    0x1c(%rbp,%rdi,<em>4</em>),%r10d<br>0x11bd3e275:   mov    %r10d,0x1c(%r8,%rdi,<em>4</em>)       </pre><pre><em>Operation: Increment Loop-Counter i (This time +4):<br>ch.styp.TestMain</em>::addArray@<em>27</em> (line <em>37</em>)<br>0x11bd3e27a:   add    $0x4,%edi                    ;*iinc </pre><pre><em>Operation: Compare Loop-Counter i, and jump to add-Block:</em>                        <em>ch.styp.TestMain</em>::addArray@<em>28</em> (line <em>36</em>)<br>0x11bd3e27d:   cmp    %eax,%edi<br>0x11bd3e27f:   jl     0x11bd3e240                  ;*goto</pre><p>Last but not least, we enforce all the features that Java has to offer and we are expecting Loop-unrolling and vector parallelism to appear in the assembly code. The x86 instruction set has the equivalent of mov and add in vector form as <em>vmov</em> and <em>vadd</em> (and variations thereof), so we expect to see these instructions in the emitted assembly code:</p><pre><em>Operation: add a[i+0..3]+b[i+0..3] and move data to c[i+0..3]:</em><br>0x112c9d300:   vmovdqu 0x10(%rbp,%r11,<em>4</em>),%ymm0<br>0x112c9d307:   vpaddd 0x10(%r13,%r11,<em>4</em>),%ymm0,%ymm0<br>0x112c9d30e:   vmovdqu %ymm0,0x10(%rdx,%r11,<em>4</em>)</pre><pre><em>Operation: add a[i+4..7]+b[i+4..7] and move data to c[i+4..7]:</em><br>0x112c9d315:   vmovdqu 0x30(%rbp,%r11,<em>4</em>),%ymm0<br>0x112c9d31c:   vpaddd 0x30(%r13,%r11,<em>4</em>),%ymm0,%ymm0<br>0x112c9d323:   vmovdqu %ymm0,0x30(%rdx,%r11,<em>4</em>)</pre><pre><em>Operation: add a[i+8..11]+b[i+8..11] and move data to c[i+8..11]:</em><br>0x112c9d32a:   vmovdqu 0x50(%rbp,%r11,<em>4</em>),%ymm0<br>0x112c9d331:   vpaddd 0x50(%r13,%r11,<em>4</em>),%ymm0,%ymm0<br>0x112c9d338:   vmovdqu %ymm0,0x50(%rdx,%r11,<em>4</em>)</pre><pre><em>Operation: add a[i+12..15]+b[i+12..15] and move data to c[i+12..15]:</em><br>0x112c9d33f:   vmovdqu 0x70(%rbp,%r11,<em>4</em>),%ymm0<br>0x112c9d346:   vpaddd 0x70(%r13,%r11,<em>4</em>),%ymm0,%ymm0<br>0x112c9d34d:   vmovdqu %ymm0,0x70(%rdx,%r11,<em>4</em>)     </pre><pre><em>Operation: Increment Loop-Counter i (This time +16):<br>ch.styp.TestMain</em>::addArray@<em>27</em> (line <em>37</em>)<br>0x112c9d354:   add    $0x20,%r11d                    ;*iinc</pre><pre><em>Operation: Compare Loop-Counter i, and jump to add-Block:</em>                        <em>ch.styp.TestMain</em>::addArray@<em>28</em> (line <em>36</em>)<br>0x112c9d358:   cmp    %eax,%r11d<br>0x112c9d35b:   jl     0x112c9d300                    ;*goto</pre><p>The appearance of the <em>ymm-</em>register indicates the use of a 256-bit wide vector operation representing 8 Integers. This proves the usage of AVX-2 in this example. (All assembly snippets were edited for better readability.)</p><p>That’s it — The default generated machine code contains vector parallelism and Loop-unrolling, as the last example proves. Therefore, a vector parallel implementation can not beat the JVMs emitted code. Auto-vectorization and Loop-unrolling are being applied so cleverly that the API-based implementation can not yield any performance uplift. It is impressive how well the JVM can optimize simple code snippets to generate the best performance on any platform.</p><h3>Let’s prove the hypothesis: The Benchmark.</h3><p>It is one thing to talk about improvements and show them in assembly code but to complete this work, it is necessary to deliver the benchmarks. The interesting question is whether the simpleSum implementation was not efficient — or whether the baseline is so well optimized that manually applied code tweaks (Vector API) cannot provide any further performance benefit.<br>For completeness reasons, different JVM configurations and native Vector API implementations have been benchmarked:</p><p><strong>No Unrolling, No Vector:<br></strong>In this case, the JVM features for Loop-Unrolling and Auto-Vectorisation are deactivated. This mode is used as a baseline for all consecutive experiments, generating the assembly code with the least optimizations applied.</p><ul><li><strong>With Unroll, No Vector:<br></strong>Loop unrolling is enabled, but Auto-Vectorisation is disabled.</li><li><strong>No Unroll, With Vector:<br></strong>Auto-Vectorisation is enabled, but loop-unrolling is disabled.</li><li><strong>With Unroll, With Vector:<br></strong>Both flags for Loop-Unrolling and Auto-Vectorization are enabled — whether this is forcing both techniques to be applied, or only optimizing based on the best case basis, is unfortunately undocumented.</li><li><strong>Java Default:<br></strong>No additional flags; The JVM runs in its default configuration.</li><li><strong>Vector Implementation:<br></strong>The code is implemented using the Vector API and therefore forced to run as Vector-parallel code; The JVM settings are left in default mode.</li></ul><p>The array lengths were chosen to represent worst-case scenarios in terms of fitment. The tests were performed on multiples of 2^n-1. Specifically, the following values were used: <em>15, 255, 4095, 65535, 16777215, 268435455</em>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*MTdEhFE4hR-utdcbPcTeww.png" /><figcaption>The benchmarks with Loop-Unrolling, Auto-Vectorisation, and combinations of both. Including comparison to native Vector API implementations.</figcaption></figure><p>The results show expected behavior; the most significant speed-ups can be seen in areas where data is kept cache-local (L1-Data and L2).<br>Additionally, the simpleSum benchmark heavily benefits from Loop-Unrolling and Auto-Vectorization already in the Java Runtime default setting! Therefore it is impossible to improve any further by leveraging the Vector API:</p><pre>+--------------------------+---------------+<br>|          Method          | Peak Speed-Up |<br>+--------------------------+---------------+<br>| No Unroll, No Vector     | 1.00x         |<br>| With Unroll, No Vector   | 1.22x         |<br>| No Unroll, With Vector   | 1.01x         |<br>| With Unroll, With Vector | 2.15x         |<br>| Java Default             | 2.06x         |<br>| Vector Implementation    | 2.08x         |<br>+--------------------------+---------------+</pre><p>The Peak Speed-up table is shedding even more light on the benchmark process: Loop-Unrolling and Auto-Vectorisation as standalone solutions only provide little benefits. But together, they contribute to a tremendous speed-up of over 2x.</p><h3><strong>Discussion</strong></h3><p>In the original blog post, I speculated about why a Vector API implementation is not making any significant speed-up compared to the primitive Java implementation. At this point, the answer is simple: <em>The JVM is so damn clever that it is impossible to beat the Just-in-Time compiler in simple cases! — </em>Full stop, no discussion!</p><p>By looking under the hood of the JVM, it is impressive to see that a combination of Loop-Unrolling and Auto-Vectorisation is needed to yield max throughput.</p><p>A hypothetical computing efficiency improvement can be estimated by comparing the two blocks of machine code. The version without Loop-Unrolling needs 6 instructions per array item, while the Version with Loop-Unrolling needs 15 instructions per four items; Therefore, a simplified estimate of 24 instructions for 4 items to 15 instructions for 4 items results in a ‘very’ hypothetical uplift of 1.6x times. This is purely theoretical!</p><p>Vectorisation should contribute a theoretical performance benefit of 4x (AVX-2). However, it is not expected in this case to see such an uplift. The overhead of moving data through the registers is just very costly compared to the primitive nature of the computational operation. Consequently, the measured speed-up is lower. The speed-up of 2x when Loop-Unrolling and vectorization are combined indicates that the Intel x86 architecture benefits from longer instruction strides in SIMD mode — without interruptions from compare-instructions or jump-instruction. The longer the CPU can run uninterrupted in its vector registers, the higher the speed-up might be. This leads to the conclusion that a ‘cold-start’ for vector instruction exists, which stalls the processor for a while. (In my opinion, it also raises the question of whether all these TFLOP numbers represent the real world or are just assembly instructions concatenated to produce the most superior numbers.)</p><h3>Conclusion</h3><p>To conclude this piece, I stick to my already often mentioned optimization statement: Your mileage may vary.</p><p>We have seen that the Just-in-Time compiler is a very capable optimizer; in simple examples, it is impossible to beat its performance. So in the future, be careful that optimizing is an art and benchmarking is an equal art. It might be worth investigating optimization options, but at the same time, it is ok to get disappointed — because Java does this so awfully well for us.</p><h3>Acknowledgement</h3><ul><li>Christoph Amrein &amp; Marco Glauser for sparing ideas and improving some thoughts.</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=92c72b97fba3" width="1" height="1" alt=""><hr><p><a href="https://itnext.io/auto-vectorization-how-to-get-beaten-by-compiler-optimization-java-jit-vector-api-92c72b97fba3">Auto-vectorization: How to get beaten by compiler optimization — Java JIT &amp; Vector API!</a> was originally published in <a href="https://itnext.io/">ITNEXT</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Java 18: Vector API — Do we get free speed-up?]]></title>
            <link>https://medium.com/@Styp/java-18-vector-api-do-we-get-free-speed-up-c4510eda50d2?source=rss-3ab3e769942e------2</link>
            <guid isPermaLink="false">https://medium.com/p/c4510eda50d2</guid>
            <category><![CDATA[vector-api]]></category>
            <category><![CDATA[simd]]></category>
            <category><![CDATA[java]]></category>
            <category><![CDATA[java-18]]></category>
            <dc:creator><![CDATA[Martin Stypinski]]></dc:creator>
            <pubDate>Thu, 24 Mar 2022 08:06:25 GMT</pubDate>
            <atom:updated>2022-04-02T04:43:15.261Z</atom:updated>
            <content:encoded><![CDATA[<h3>Java 18: Vector API — Do we get free speed-up?</h3><h3>Motivation</h3><p>One of my professors at university always tried to convince me: “There is no such thing as free lunch.” But, I have to admit that I never got a free lunch at university, and there is also no magic formula to accelerating a piece of software.</p><p>Java Vector API provides an abstraction layer to data-parallel capabilities of modern CPUs. As different processor architectures come in different flavors, there is no simple solution to leverage platform-specific capabilities in software. It is often necessary to write code in a platform-specific way and leverage the platform’s specific capabilities to see stellar performance benefits. The Vector API tries to enable developers to write data-parallel software in a very platform-agnostic way. The developer doesn’t need to be aware of the runtime target.</p><p>This blog post tries to explore the possibilities provided by the new Vector API on some examples and whether it is worth exploring a potential implementation or not for specific use cases.</p><h3>What is Java Vector API?</h3><p>To explain how the Java Vector API abstraction works, we need to explore different CPU architectures and provide a basic understanding of data-parallel computation. However, the concept is not so new. It has existed in C# for a while and has proven to be a good approach to leveraging data-parallel computation on modern hardware architectures.</p><p>In contrast to a regular computing operation, as in 1+1, where two “pieces of data” are added in one operation, a data-parallel operation is executing a simple operation (e.g., +) on multiple “pieces of data” at the same time. This mode of operation is called SIMD (Single Instruction, Multiple Data), whereas the traditional way of execution is called SISD (Single Instruction, Single Data). The performance speed-up results from applying the same operation on more than one “piece of data” within one CPU cycle. As a simple example: Instead of adding each element of an array A with each element of an array B, we take chunks of array A and array B and operate simultaneously. The two modes are illustrated below and should provide evidence of why SIMD should increase computational performance.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/724/1*8vkZM2pm68dYveLfvrPbiA.png" /><figcaption>The illustration of a conventional CPU operating mode on the left: One instruction processes one “piece of data”. On the right side: One instruction is applied to multiple “pieces of data”. SISD vs SIMD — Source: <a href="https://ichi.pro/de/apples-m1-secret-coprozessor-111709032268257">https://ichi.pro/de/apples-m1-secret-coprozessor-111709032268257</a></figcaption></figure><p>As processors come in different μArchs (x86, ARM), their SIMD implementations differ significantly. For example, Intel and AMD share MMX, SSE, AVX, while ARMs SIMD interpretation is called NEON. AVX-512 is currently only supported on Intels latest high-end processors. In 1993, with the launch of MMX, it was possible to operate on 64 Bits (two Integers (4 Bytes)) simultaneously. Therefore MMX enabled 1+1 and 2+2 within the same computing cycle; this provided a theoretical speed-up of around 2x on Integer additions. Fast-forward to 2022, AVX-512, a 512 Bit wide instruction set, trickles down to consumer notebooks. This instruction set can handle up to 16 Integer operations simultaneously! Hypothetically, a performance up-lift by a factor of 16x should be feasible. In addition to the broader data-width, some combined operations are implemented too, so occasionally, even two or three operations can be performed during the same cycle, as in Fused-Multiply-Add (FMA): c = c + a*b. These fused operations help manufacturers to claim 100x speed-ups. (On very few and highly-specific use-cases.)</p><p>This introduction concludes that a well-elaborated abstraction layer has to consider that the developer should not care at all about the μArch the code will run on. On the other hand, the JVM needs to emit the instruction depending on the platform. Each platform has strengths and weaknesses depending on vendor-specific implementations (AMD or Intel). The provided ‘one-API-fits-it-all’ solution is an ambitious endeavor. In my opinion, this API will provide an impressive performance up-lift, but to reach stellar results, platform-specific fine tunning will be needed.</p><h3>Understanding the Basics: Simple Sum</h3><p>To start with a simple example, we can have a detailed look at the following code snippet:</p><pre>public static int[] simpleSum(int[] a, int[] b) {<br>    var c = new int[a.length];</pre><pre>    for (var i = 0; i &lt; a.length; i++) {<br>        c[i] = a[i] + b[i];<br>    }</pre><pre>    return c;<br>}</pre><p>The same code translated into a data-parallel accelerated code by means of Vector API:</p><pre>private static final VectorSpecies&lt;Integer&gt; <em>SPECIES </em>= IntVector.<em>SPECIES_PREFERRED</em>;</pre><pre>public static int[] vectorSum(int[] a, int[] b) {<br>    var c = new int[a.length];<br>    var upperBound = <em>SPECIES</em>.loopBound(a.length);<br><br>    var i = 0;<br>    for (; i &lt; upperBound; i += <em>SPECIES</em>.length()) {<br><em>        </em>var va = IntVector.<em>fromArray</em>(<em>SPECIES</em>, a, i);<br>        var vb = IntVector.<em>fromArray</em>(<em>SPECIES</em>, b, i);<br>        var vc = va.add(vb);<br>        vc.intoArray(c, i);<br>    }</pre><pre><em>    // Compute elements not fitting in the vector alignment.</em><br>    for (; i &lt; a.length; i++) {<br>        c[i] = a[i] + b[i];<br>    }<br><br>    return c;<br><br>}</pre><p>Au contraire, this code needs a little more clarification. Before the code can run and make use of SIMD acceleration, the data-width has to be established. AVX compatible CPUs can handle 256 Bits while AVX-512 can provide 512 bits of data-width:</p><pre>private static final VectorSpecies&lt;Integer&gt; <em>SPECIES </em>= IntVector.<em>SPECIES_PREFERRED</em>;</pre><p>Consequently, we need to configure the loop size correctly. The <em>simple</em> for-loop uses <em>i++</em> to increment the index by <em>one</em>; in this example, it is needed to shift according to the data-width of the SIMD registers. In the case of an Integer operation running on AVX-512 (512 Bits), we have to increment by <em>16</em>. The first iteration performs the operations a[0]+b[0] up to a[15]+b[15]. The next operation performs the same on a[16]+b[16] up to a[31]+b[31], and so on…</p><pre>//Determines the last index that fits the registers and cuts off any &#39;overhanging&#39; items.<br>var upperBound = <em>SPECIES</em>.loopBound(a.length);<br><br>var i = 0;<br>// Increment by the data-width!<br>for (; i &lt; upperBound; i += <em>SPECIES</em>.length()) {<br>   ....<br>}</pre><p>Finally, all the remaining items, which didn’t align within the data-width need to be handled. Therefore the operation has to be performed in a non-parallel way starting at the first item that was not touched by the vector-loop:</p><pre>for (; i &lt; a.length; i++) { <em>// Cleanup loop<br>    </em>c[i] = a[i] + b[i];<br>}</pre><p>The Vector API code might look a little odd, but the design is very similar compared to my previous experience in C#.</p><h3>Getting up to speed: Fused multiply-add (FMA)</h3><p>Another essential operation is the so-called fused multiply-add (FMA), also known as the multiply-accumulate (MAC) operation. The operation computes the product of two numbers and adds that product to an accumulator: c = c +(a * b).</p><p>It is used to compute dot-products, matrix multiplications, polynomial evaluation (Horner’s rule), Newton’s method and Convolutions (CNN). Its variety of applications did not determine the choice for this example, but there is almost no store instruction overhead. The result is a simple Float (4 Bytes), and two arithmetic operations are computed simultaneously. (Potential Speed-up!)</p><pre>public static float vectorFMA(float[] a, float[] b){<br>    var upperBound = <em>SPECIES</em>.loopBound(a.length);<br>    var sum = FloatVector.<em>zero</em>(<em>SPECIES</em>);</pre><pre>    var i = 0;<br>    for (; i &lt; upperBound; i += <em>SPECIES</em>.length()) {<br>        <em>// FloatVector va, vb, vc<br>        </em>var va = FloatVector.<em>fromArray</em>(<em>SPECIES</em>, a, i);<br>        var vb = FloatVector.<em>fromArray</em>(<em>SPECIES</em>, b, i);<br>        sum = va.fma(vb, sum);<br>    }<br>    var c = sum.reduceLanes(VectorOperators.<em>ADD</em>);</pre><pre>    for (; i &lt; a.length; i++) { <em>// Cleanup loop<br>        </em>c += a[i] * b[i];<br>    }<br>    return c;<br>}</pre><p>The code is similar to the example provided in the first sample. A data-parallel loop and a cleanup loop to collect the missing items at the end of the array. The only new feature that needs to be introduced is the following line:</p><pre>var c = sum.reduceLanes(VectorOperators.<em>ADD</em>);</pre><p>All FMA-operations are executed in a data-parallel way in the upper part of the code. Therefore, the resulting data is stored in the provided data-width (in the case of AVX-512: 16 Floats). Therefore, these 16 Floats need to be reduced to 1 Float utilizing the add-operator.</p><h3>Lets talk performance: The benchmark</h3><p>All this effort would be worthless without any proof of performance. So for all the benchmarks, a modern Intel Xeon Gold 6212u (μArch: Cascade Lake SP) was used. The CPU is capable of AVX-512, which is the latest SIMD instruction set on the market and the one with the broadest data-width. While not all current platforms have AVX-512 capabilities, reproducing these results depends on the device. Further, the benchmark was done in a well-cooled environment as thermal throttling can imply problems to yield reproducible results. (Intel tends to get “warm”).</p><p>The array lengths were chosen to represent worst-case scenarios in terms of fitment. The tests were performed on multiples of 2^n-1. Specifically, the following values were used: <em>15, 255, 4095, 65535, 16777215, 268435455</em>.</p><p>The benchmark was performed 100-times and ran on the JMH framework to have a reproducible clean baseline. The deviation between all the runs is within a margin of 5%. The metric used to determine the runtime is ops/ms, which is the inverse of the runtime. The higher the value, the higher the computation speed for the given array size.</p><p>The metric is the total throughput of each function measured in ops/ms</p><p>The code is available on Github: <a href="https://github.com/Styp/java-vbench">https://github.com/Styp/java-vbench</a></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*89HbWUOFp9AmBHcUQfLdVA.png" /><figcaption>non-Vector: Simple Sum, as in the provided example; Vector: A vector accelerated version of SimpleSum as in the provided example.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*w_Bx5I2vgSVGKSp4zA89Qw.png" /><figcaption>non-Vector: Simple implementation of multiplying and adding the two arrays in a loop; Vector: data-parallel FMA implementation.</figcaption></figure><p>The light gray colored areas indicate the processor’s cache size. The first benchmark (SimpleSum) needs to fit at least three arrays into the cache. Only two arrays need to fit into the cache in the second benchmark; therefore, the gray areas differ by a factor of 1/3.</p><h3>Discussion</h3><p>The benchmark is conclusive and proves one crucial point: Vector API can provide a significant speed-up. In the case of FMA, we see a speed-up of 16x. But not so fast, this is getting complicated, so let’s start with the beginning of the story:</p><p><strong>Simple Sum Benchmark:</strong></p><p>The first benchmark shows no significant gain whatsoever. There is just a tiny difference between using simple loops compared to data-parallelism. The visualization can not give the benchmark the needed credit because the difference is tiny. The performance difference between the methods is more significant than the variance over multiple runs of the same method:</p><pre>Benchmark  ArraySize<br>SimpleSum         15    660843.630 ± 1193.972  ops/ms<br>SimpleSum        255    122504.912 ±  525.374  ops/ms<br>SimpleSum       4095      6076.249 ±   33.375  ops/ms<br>SimpleSum      65535       387.500 ±    2.456  ops/ms<br>SimpleSum    1048575        14.238 ±    0.008  ops/ms<br>SimpleSum   16777215         0.588 ±    0.004  ops/ms<br>SimpleSum  268435455         0.036 ±    0.001  ops/ms<br>SumVector         15    683927.065 ± 1497.257  ops/ms<br>SumVector        255    125584.998 ±  553.290  ops/ms<br>SumVector       4095      6080.694 ±   38.225  ops/ms<br>SumVector      65535       380.024 ±    2.669  ops/ms<br>SumVector    1048575        14.503 ±    0.021  ops/ms<br>SumVector   16777215         0.612 ±    0.004  ops/ms<br>SumVector  268435455         0.035 ±    0.001  ops/ms</pre><p>The similarity of the results can have various (speculative) reasons:</p><ul><li>Java “unrolls” the data-parallel part because it’s not <em>worth</em> running the code this way. The difference between the runs indicates that it does not converge towards the same byte code.<br>(Was not investigated further but could be done with more profiling.)</li><li>There is a significant overhead attributed to enabling AVX-512. It just needs a moment to get going, and this might be a lot of time compared to the raw computation time; therefore, there is no performance increase.</li><li>The overhead of aligning and copying the data into the proper registers is significant and contributes to diminishing returns.</li><li>Copy-Back ( vc.intoArray(c, i); ) is time consuming.</li><li>A combination of multiple factors mentioned is also a possible option. Other effects happen at small array sizes, and other effects occur at large array sizes.</li></ul><p><strong>Fused Multiply-add (FMA) Benchmark:</strong></p><p>The FMA benchmark shows a peak speed-up of up to 16x, an impressive figure for a single-threaded benchmark only leveraging data-parallelism. Nevertheless, there are some profound discoveries:</p><ul><li>Vector API is very efficient in crunching data that fits comfortably in the L1 + L2 cache. The performance of more giant arrays is still faster by 2x, compared to the non-SIMD implementation.</li><li>An average speed-up of 2x might sound like a decent improvement. A question that stays on the plate is whether it is worth the effort to rewrite an entire algorithm or not for this little benefit. Further, AVX-512 might not be available to all the processors, so results differ.</li><li>Javas just-in-time compiler is very impressive in predicting data preload without stalling the process. Otherwise, the almost linear behavior of the non-vector implementation is barely explainable.</li></ul><p><strong>General observations:</strong></p><ul><li>The performance is strongly dependent on the complexity of the operation. More complex operations (FMA) tend to perform better than simple operations (SimpleSum). A more significant speed-up can possibly be seen with more time spent on SIMD mode.</li><li>The API is very straightforward, but the way of thinking has to adapt. Not all sequential algorithms can be easily ported to Vector API code.</li></ul><h3>Conclusion</h3><p>To conclude this piece, I think the Vector API is a significant step forward to provide a good SIMD abstraction layer for a high-level programming language across many modern platforms. The following points are my personal take-aways from this exploration of the framework in its latest iteration:</p><ul><li>Vector API is not a “free lunch”; it is not as simple as a “Stream.parallelFor()” and is therefore limited in its everyday usability.</li><li><strong>Important:</strong> SIMD has nothing to do with multithreading!</li><li>Algorithms without inter-data dependencies can enjoy a significant speed-up if implemented in a data-parallel way. The more computation has to be done, the better the result, and memory-copy is less of a time-penalty as more time is spent on the computing part.</li><li>One of the most impressive parts of this benchmark was to find out how highly optimized the JVM is. The almost linear “non-Vector” FMA benchmark shows strong memory preloading capabilities, which are difficult to beat!</li><li>Vector API is here to stay for sure; the API is very similar to my experiences with C#. Further, I think it will be possible to see more performance benefits with time. The project will mature, and so will the performance increase with time.</li></ul><h3>Acknowledgments</h3><ul><li>Christoph Amrein, Marco Glauser, Kirusanth Poopalasingam and Marc Juchli for reading it, challenging the ideas and providing some input on how to explain things even better — Thank you!</li><li>Dr. Luc Bläser &amp; Dr. Thomas Bozek for “scrutineering” my plots and make them more readable.</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c4510eda50d2" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>