By the way, I trust artificial intelligence (AI) and large language models (LLMs) no more than my Tarot cards.

WARNING: This article contains beautiful Tarot cards that can give you a smile in your heart, but it also contains supernatural themes that may be incompatible with your belief. Viewer discretion is advised.

How I Became A Tarot Reader

I started learning Tarot cards and its use in divination back in high school in 2002 or 2003, when I was fascinated by an anime character who uses those cards. My first impression of those cards was that they were magical and mysterious. One can tell the future by simply drawing cards from the deck. I never believed in fortune telling or magical power in real life, but I wanted to learn about Tarot because it was just… err… cool.

Despite the fact that Tarot was not really popular in China back then (except among teenagers who also thought Tarot was cool), I managed to find plenty of learning resources on the Internet. One useful web site was Learning The Tarot maintained by Joan Bunning who kindly provided this comprehensive tutorial and reference book online free of charge. There was also a large online community of Tarot users in the form of personal web sites, forums, etc. People recommended their favourite decks, and some even creatively invented their own spreads.

Looking back from 2026, I feel that such web sites have been a treasure of the Internet. Nowadays people seldom make personal web sites, but tend to move their activities to social networks controlled by a few monopolising big tech companies. This is unfortunate because valuable documents cannot be conveniently archived, and may simply vanish if some companies suddenly go bankrupt.

Cards That Take A Lifetime to Understand

One interesting thing about such an occult item is that I can find as many versions of its history as the number of books/articles I can find. Some claimed that Tarot originated from ancient Egypt, Greece, Rome, Persia, China, or [insert your favourite region or culture here], and was a gift from gods. Others did their researches and claimed that Tarot started as a game in Italy during Renaissance, and was not used as a tool for divination until the 19th century. Anyway, modern Tarot decks are based on older ones that have assigned divinatory meanings to each card, and the Rider-Waite Tarot was one of the most influential decks in the world.

To me, a Tarot deck is a book, a story book about different stages of life, much like the Book of Change (a.k.a. Yi Jing or I Ching). (That also explains why Tarot cards are sold in book stores.) The major arcana cover the life of The Fool, which can be interpreted as any person. The Fool was born foolish (or innocent if you prefer). As a child, He discovered the world by interacting with things around him, and became aware of things beyond his knowledge. He felt the love of his mother and father, received education as he grew up, and fell in love with another person. After that, he experienced many challenges in his life, got himself into a major adversity and out, and eventually faced the final judgement and once again became one with the world. The minor arcana complement the major arcana, each displaying an additional moment of life. The minor arcana are categorised into wands which represent creativity and passion, cups which represent emotion and love, swords which represent rational thinking and courage, and pentacles which represent reality and wealth.

The fact that each card has well-known meanings has allowed artists to create many different versions of Tarot decks. Artist paint the cards in their own styles, following their own interpretations of the cards. For example, the Five of Wands represents discord. Different decks will depict humans or animals fighting each other, with their eyes open or closed, depending on their fighting styles (or art styles if you prefer). Therefore, Tarot cards are not only a game or a divination instrument, but also a piece of art. Before I realised, I have bought 9 decks in the past 20 years or so, and the motivation of buying has usually been ‘Wow! Those cards look so good!’

It takes a lifetime to really understand the meanings of the cards despite they are well-explained in books. One needs to live long enough to experience all the moment of life depicted. That was the main obstacle for me when I first attempted to learn Tarot at the age of 16. The cards were just confusing. Neither remembering the meanings of the cards nor interpreting the cards using my intuition seemed to work. But as I grew up, I lived through fights, lies, betrayal, anger, fear, despair, things that I thought I understood but not, things that I had been taught again and again but were lies, morons who thought they were geniuses, things that started with great confidence but went horribly wrong, etc. And I also experienced love, learned to identify people whom I can trust, learned to refuse to be treated like a doormat, and tasted the fruit after working hard. When I look at the cards again after all those years, everything suddenly becomes crystal clear. I have been the fool all along.

Tarot Cards Are Not Magic

There is no magic in Tarot cards. Modern decks are likely painted using raster or vector graphics software, and printed using computer-assisted machinery, all of which are just too un-magical to computer scientists. This means we can’t simply ask yes-or-no questions and expect a correct answer. It is more advisable to ask open-ended questions and let the cards guide our thoughts.

The picture on the right is an example of choice-making spread.

Note that as an example, I am using the major arcana 0 to 4 to mark the positions, but in real-world reading, cards are drawn at random (or according to your ‘intuition’ if you prefer).

• Position 0 represents the current situation.
• Position 1 and 2 represent the consequences of choice A and choice B, respectively.
• Position 3 and 4 represent the outcomes of choice A and choice B, respectively.

The point is, the cards won’t tell us which choice is ‘right’ or ‘wrong’. Humans do the interpretation, and humans make the final choice.

Cards drawn at random carry no more information than what the Tarot reader already knows (in the information theory that means no information at all). The cards are only hints that lead us to think in certain directions. Only human beings can think. For example, the Three of Swords means feeling heart-broken. But when reading, humans need to figure out (1) who is doing the harm and who is getting hurt, and (2) what kind of harm it is. Only those involved in the event know the answers. The cards don’t.

Sometimes Tarot cards do carry information. Tarot cards are a story book, and with every story comes the lore behind it. The Strength shows a woman taming a lion gently with her bare hands, which reminds us that the real strength is not always about brute force. The Tower is destroyed by a lightning strike, releasing people imprisoned within. It represents sudden changes and destruction, but also reminds us that destruction can sometimes be a good thing.

That is Tarot, a book that guides our thoughts and reminds us of wisdom that we have already learned. And Tarot reading is no more magical than opening a random page of a book and seeing if the knowledge can help us solve our problems. That’s how Tarot reading really works.

Debugging Software With Tarot Cards

Sometimes we need to interpret the cards creatively.

Several years ago, a colleague of mine was working on a compiler project, and he asked me about a bug where the code generated by his compiler went wrong when calling a function. I happened to have a Tarot deck at hand, and I drew one card from the deck. It was the Six of Pentacles, reversed. In conventional interpretation, the Six of Pentacles means giving or receiving financial (or other forms of) support. But I suddenly noticed that the card was showing a person giving coins to another, and coins have value. ‘Value? Passing value(s)?’ I thought. I told my colleague, jokingly, ‘Six of Pentacles reversed means there is an error in value-passing. Did you pass the argument in the wrong register?’ And, as it turned out, that was exactly what happened! He fixed the register and the bug disappeared!

It was a coincidence that the card I drew was the Six of Pentacles, and it happened to be reversed. But that card led me to think in the direction of value passing, a concept in programming. It was my knowledge about compilers that reminded me that calling convention governs value passing in function invocation (which my colleague asked about in the first place), and it was my intuition as a compiler engineer that something was likely to go wrong when choosing the right register to pass arguments or return values.

After all, humans debug the program, and Tarot cards only provide the hint. Anyone without prior experience in programming would have stared at the reversed Six of Pentacles for hours without even knowing what to investigate, and it was unlikely for them to find the cause of bugs using Tarot cards.

Again, randomly drawn cards don’t give us more information than what we already know.

AI Is No More Trustworthy Than Tarot Cards

We can generalise that statement to artificial intelligence (AI) and large language models (LLMs). AI is only as trustworthy as the knowledge we already have.

Recently, my wife tried to find out why the stock price didn’t go up, and LLM generated her a lengthy report, listing many plausible causes. While urging her to ask the LLM for the concrete news reports that supported its views, I picked three cards from my Tarot deck, as shown in the figure on the right, asking the question:

Tarot cards, please tell me something about the price of a stock which I have no idea what it is.

• Seven of Pentacles means assessment, that is, evaluating one’s work after reaching a milestone.
• Eight of Cups means moving on, that is, leaving things behind in search for something else.
• The Hermit means choosing to be alone, staying away from others.

If we put them together, we come up with an explanation:

After an evaluation, existing investors left that company behind in search for better investment options. Other investors stayed away, hesitating to invest in that company.

I showed my wife this seemingly plausible but rootless explanation. To my surprise, my wife told me that was exactly what happened! That company gave an almost perfect quarterly report, but its stock price dropped right after that.

Did the Tarot cards use its magic to come up with an explanation? No, of course. The cards are random, and I just used my intuition. Capitalists seek maximum profit, and they won’t stay with one company if it has reached its apex.

But did the LLM understand economy? I tried asking LLM by myself, and it generated a lengthy report for me, too. I then asked it for evidences that support its views, and it listed several news reports, written by people I don’t know, from the news website run by the same company running the LLM. The LLM even tried to show that two events are causal because they are temporally interleaving. I am not an economist, so I don’t know enough to judge whether the news reports are trustworthy. But as a computer scientist, I know how superficial and unreliable news reports from mass news agencies about computer technologies can be. And I know very well about spurious correlations, and understand correlation does not imply causality.

That shows that I can’t fully trust LLM about things that I don’t understand in the first place. Since I know how bad the AI explains source code, I know that only real economists know how much truth the LLM is telling.

The problem of current LLM-based AI is that they are trained from garbage. Humans with knowledge about a specific field can identify trustworthy information and discard nonsense. AI companies, on the other hand, crawl the web and feed the AI with everything they find. They then train the AI to generate articles that please the readers instead of being loyal to the truth.

We may even claim that three randomly drawn Tarot cards are more trustworthy than the LLM because at least it reflects the knowledge the reader actually has.

Tarot Cards in The AI Apocalypse

What’s worse, there are people trying to influence the AI to their advantage. They write their advertisements in a style like an encyclopaedia with elaborate use of bullet points, and tricks the AI into thinking their articles list facts. Consulting companies for influencing AI already exist, just like search engine optimisation (SEO) which existed decades ago. And we know what happened after SEO: thousands (if not millions) of automatically generated web sites full of nonsense. They polluted the Internet and made search engines almost useless.

What’s even worse, AI companies are trying to make their AI prompts the entrance of the Internet. Some even offered free milk tea to encourage consumers to install their AI clients and order food using their AI. Once AI monopolises the user interface, AI companies will have full control over what users see. Merchants that pay the most for AI services will gain maximum visibility, and those who don’t gets hidden forever. The rat race will destroy most small business that are not profitable enough to pay the AI services. Actually, this is already happening in Beijing without AI. With the high operation cost, including house rent, many fancy small restaurants closed, leaving only food chains offering boring pre-packaged food.

Sooner or later, Tarot cards drawn at random may provide more informed advices for finding the next restaurant to go to than asking the AI. If we go to smaller cities, such as Tianjin, where the low operation cost allows many small good restaurants to survive, picking restaurants at random can give surprisingly good results.

Sooner or later, it may be more advisable to write a summary using Tarot reading instead of AI. At least Tarot cards reflect what we humans already know, and we can claim full authorship instead of being caught for plagiarism.

And have you tried writing a story by picking a sequence of 78 Tarot cards? Someone actually tried that. Isn’t that more fun than asking the AI to make up a story for you?

Epilogue

I encourage everyone to learn Tarot reading (unless your belief forbids you from doing so, of course). Tarot cards are a open standard, and are well-documented. And they look beautiful, don’t they? With the popular Rider-Waite Tarot freely available in the public domain, everyone can create derived work in their own style.

About The Deck In This Blog Post

The cards I used are from the Serenity (a.k.a. 风和日丽 in Chinese) deck from the WohStudios. It is based on the Rider-Waite Tarot, but is more gentle and cute in style. We can’t find dramatic expressions of joy or pain on the cards, but that is enough for sensitive readers to feel the spirits of each card.

A: Most objects need finalisation.

I attended the ISMM’2025 conference and presented a paper. I enjoyed the presentations and talked with interesting people. What I found more interesting was how people do (real-world) garbage collection in Seoul, South Korea.

WARNING: This article contains nerdy languages.

The Paper

The paper I presented was Reworking Memory Management in CRuby: A Practitioner Report. It summarises our multi-year effort of integrating MMTk into CRuby, and it is full of challenges. The paper is fully open-access. You can download a copy here or from the ACM digital library at no charge. The organisers also published the video recording of my speech on YouTube.

The Language

The conference was held in Seoul, South Korea. This was the first time I visited a non-English-speaking foreign country.

The writing system was a challenge to me and my colleagues during the trip. If I went to a country that uses Chinese characters (such as Japan), I (and my Chinese friends) could understand the Chinese characters even without knowing their pronunciations in the foreign language. (But I actually learned Japanese before.) If I went to a country that uses Latin-based alphabets (such as most European countries), I might be able to spot words that were spelled similar to English and guess their meanings. But when I looked at Korean letters, I couldn’t do anything to them. I didn’t know how they are pronounced, and I didn’t know what they mean.

Fortunately, as an internationalised city, I could find English text in many places, including road signs, corner shops, toilets (sometimes written as ‘restroom’ as in the United States), underground railways, and police stations. Some roads even have official Chinese names on the road signs. In busy business areas like Myeongdong, almost everything is written four languages: Korean, English, Japanese and Chinese.

Not all Korean people speak English well. Staffs at big hotels and big shopping malls usually speak fluent English, and some of them can even speak Chinese.

Corner shop staffs and taxi drivers can speak basic English, but usually not that fluently. In some traditional restaurants, the staffs often cannot speak other languages. In such situations, we found translation software very handy. Those modern AI-based apps allowed us to take a photo and translate the text on the picture. Although none of my colleagues speak Korean, we managed to order authentic Korean food by translating the menu and communicating with the waiters with gesture languages.

And we sometimes find that we need translation service in unexpected places, such as the remote controls of air conditioners, the control panels of laundry machines, and the control panel of electronic bidets which are cute little devices that wash your private parts after using toilets. Again the AI-based translation software made it quite convenient.

Read the Spec

As a programmer, when I see a program in a programming language that I don’t understand, I read the documentation, and sometimes its language specification if there is one. I realised that I could do the same for human languages. I searched for the documentation…

In the ancient time, the Korean used the Chinese writing system. However, there is a semantic gap between the Korean and the Chinese languages. For this reason, average Korean people at that time couldn’t express themselves efficiently in Chinese, just like the Python programming language cannot be implemented efficiently on a high-performance JVM without language-specific optimisations.

With great sympathy to his subjects, the ancient King Sejong invented a new writing system optimised for the Korean language, with the explicit goal of making it easy to learn and convenient to use for everyone. He wrote the language specification, a.k.a. Hun Min Jeong Eum (literally ‘Teaching of the Proper Sound for the People’), which not only specified the rules to pronounce and write the characters, but also introduced the rationale behind the visual design.

King Sejong wrote Hun Min Jeong Eum in Classical Chinese (obviously he couldn’t write a meta-circular spec due to bootstrapping issues), which made it easy for a Chinese like me. The writing system was a genius invention. Each letter is a diagram of tongue or mouth position, making it very easy to remember. For example, ‘ㄱ’ resembles the shape of the tongue root closing the throat, giving it the /k/ sound; while ‘ㄴ’ resembles the shape of the tongue touching the hard palate, giving it the /n/ sound. I spent an hour watching a few video tutorials about basic Korean pronunciation and vocabulary. Although it still didn’t enable me to make the most basic conversations, it allowed me to see a Korean character and know how it is pronounced. Knowing the words ‘서울’ (Seoul) and ‘우유’ (milk) also allowed me to locate milk instead of soybean juice or alcohol when buying breakfast at corner shops. (Don’t mistake me. I like soybean juice, too.) And I noticed that some Korean words (such as ‘소화전’ which means ‘fire hydrant’) are pronounced very similarly to their Chinese counterparts (‘消火栓’).

Garbage Collection

In computer science, garbage collection refers to the memory management scheme that automatically recycles objects in the memory that cannot be accessed by the program. In real world, garbage collection refers to a similar activity, i.e. recycling objects that we no longer need.

The bad thing is, nowadays we human beings are generating more garbage than ever. We need to take action before our world is buried in garbage.

Reduce, reuse and recycle

I like the slogan reduce, reuse and recycle.

Firstly, we should reduce the amount of garbage we generate, like how the Lucene indexing engine once changed its API and used mutable Attributes to reduce unnecessary allocations of objects. When I was young, I carried my water bottle with me when I went to school. But nowadays I usually buy bottled water from stores when I travel, especially on international trips where I couldn’t take excessive amount of liquid past security.

Secondly, if I really have to buy bottled water from stores, I can still reuse the bottle by refilling it instead of throwing it away. The apartment where I stayed was equipped with a water purifier, so I usually carried one bottle of purified water with me when I left for the conference, saving me one bottle of water (that is, 1000 Korean Won) every day.

Then we would need to recycle the remaining garbage we generated. However, despite the technological advancement in the 21st century, humans are still required to manually sort garbage into categories before it can be recycled. The garbage categorisation system varies from country to country. In South Korea, they categorise recyclable garbage into glass, plastic, vinyl and (clean) paper.

Finalisation

In computer science, finalisation refers to the actions to be taken when an object is determined to be dead. It is a surprise that the similar actions are required in real-world garbage collection, too.

Most garbage can be categorised straightforwardly, but there is a catch. If a water bottle has a vinyl wrapper on it, it must be removed because it belongs to a different category. As shown in the picture to the right, there are instructions on the water bottle that tells me to peel off the vinyl wrapper along the dotted lines. Then I need to wash the bottle, and then dispose the vinyl wrapper into the ‘vinyl’ bin, and dispose the bottle itself into the ‘plastic’ bin. Similarly, we are supposed to wash milk cartons and other containers.

As you can see, many objects need to be finalised before they can be recycled. The experience of doing garbage collection in Seoul is similar to that in CRuby, albeit not that bad. In CRuby, as we explained in Section 4.5 of our paper, almost all objects need finalisation, just like doing GC in Seoul.

In Public Areas

In public areas, such as in the street or at the airport, garbage bins usually come in only two categories, namely ‘recycle’ and ‘waste’. I suppose someone still needs to further categorise the garbage, but it makes the life easier for the tourists.

However, I felt there were fewer garbage bins in the streets of Seoul compared to other cities like Beijing and Canberra. The organisers of the conference told us that Seoul removed many of the garbage bins in the city for security reasons. Several decades ago, some bad guys put dangerous items into public garbage bins, which caused public security concerns. Now garbage bags are all transparent, again for security reasons.

At the Conference Venue

Considering that most foreigners are unfamiliar with the Korean garbage categorisation system, the conference organisers kindly arranged volunteers to patrol the conference ground and collect garbage, such as plastic bottles, that are left on tables. I found it whimsical to present a paper about garbage collection in a conference which was itself garbage-collected.

Epilogue

The trip went on very well. My peers and I presented our papers, and I met our collaborator Peter Zhu in person. I also met some of my ex colleagues from Huawei, and they had been making a very interesting programming language Cangjie and had extended the LLVM to better support garbage collection. Unfortunately, I also found that some people, including professors from well-known universities, still having strong misconceptions about garbage collection and reference counting. That’s why we still need to work hard to make a garbage collection framework because not everyone knows how to do it right.

WARNING: Contains harsh words. Viewer discretion is advised.

The Open-Source Promotion Plan (OSPP)

The United States started a trade war against China several years ago, and my former employer was on the ‘Entity List’. Depending on your political stance, you may support one side or the other. But the trade war raised a real concern for every company about their software supply chain. If your company suddenly appears on the Entity List of some country (including but not limited to the US), your favourite software may immediately become unavailable. For instance, MATLAB is no longer available to the Harbin Institute of Technology.

This is where free software (a.k.a. free open-source software, or FOSS for short) comes into play. What will you fear for if you have the complete source code (and probably the entire revision history) in your hard drive (not in the ‘cloud’), and the contributors have given you a perpetual, worldwide, non-exclusive, no-charge, royalty-free, irrevocable license to run, copy, distribute, study, change and improve the software? Free software (and free hardware, too) is the ultimate answer to protectionism. Since the trade war started, Chinese companies and the government started to embrace free software more than ever. Some government agencies even switched to domestic GNU/Linux distributions as their primary working environments for average workers.

Here is a photo taken from the computer science section in a Xinhua Book Store in Beijing. The book store is currently under refurbishment, so only a small fraction of books are displayed. Even if you don’t read Chinese, you can still recognise books about open-source technologies such as Linux, Apache Pulsar, Kotlin, Python, Java, OpenCV, Qt 6, Scratch, Go, R, OAuth2 and PostgreSQL. This means free software is no longer a niche technology in China, but a technology on popular demand.

The Open Source Promotion Plan (OSPP) is an event organised by the Institute of Software, China Academy of Science (ISCAS). According to OSPP’s official website, it is an explicit goal of OSPP to ‘build the open source software supply chain together’. Similar to Google Summer of Code (GSoC), OSPP funds students (not limited to Chinese nationals) to participate in free software projects for three months (from July to September) in Summer.

• For students, such events give them motivations to make contribution, for the love of FOSS or just some extra cash.
• For FOSS projects, such events give them an opportunity to attract contributors, and also get some low-priority tasks done while main contributors are busy with high-priority issues.
• For the organiser, ISCAS, and the Chinese government backing it, this event encourages more people to participate in FOSS development, which will eventually yield a stronger free software community and help both Chinese users and FOSS users worldwide to counter protectionism.

That is a win-win-win situation.

The MMTk project participated in the OSPP in 2023, and I was the project representative of MMTk. Two students worked with MMTk, and I mentored one of them. The good thing is, both students finished their tasks, and we are grateful to ISCAS for organising such an awesome event, and to the students for their contributions. However, the experience of participating in OSPP is not 100% pleasant, and I’ll elaborate.

The good

I have always been a FOSS enthusiast. In late 2000s and early 2010s, I attended many off-line activities related to FOSS in Beijing (because I studied in Beijing). That included several student societies in my university, the Software Freedom Day, activities from local user groups such as the Beijing Linux User Group, the Beijing GNOME User Group, etc. Then I went to Australia for my PhD, where I enjoyed exciting talks and pizzas with the Canberra Linux User Group. After I returned to China, I didn’t find much chance to get together with local communities due to work pressure and COVID19. I missed the days when FOSS lovers (including both Chinese and foreigners working in Beijing) get together once a month, bringing laptops, and coding for fun.

I heard about OSPP in late 2022, and thought MMTk should participate in the next year in order to let more people know about MMTk, and probably let more people know how awesome the Australian National University (ANU) is, too. I couldn’t wait telling FOSS lovers that we are doing interesting researches on memory management and working on open-source projects with collaborators from many different countries. And we did. We applied for participation in OSPP’2023, and we were accepted.

Meeting the organisers

In early 2023, I met an OSPP organiser in an off-line meeting, and I was very excited to know that they were working hard to promote free software. The organiser told me that OSPP organisers had visited several universities in different cities in China in order to get more students know about OSPP and free software in general. The organiser also told me that although free software was already very popular among top-tier universities in Beijing, it was far from true in lower-tier universities in smaller cities. I appreciated their efforts. It takes time and energy to get people aware of free software, and it is harder for them to understand the spirit of software freedom, but it is worth trying.

During the whole OSPP’2023 event, the organisers helped us with the process of registration as well as overcoming errors of their poorly engineered website (I’ll elaborate in the next section). They tried their best keeping the event running.

The organisers also invited participating communities to submit introduction videos so that they can help promoting their projects by publishing the videos on behalf of the communities. Professor Steve Blackburn, the leader of the MMTk project, gladly made a video to provide a brief introduction to MMTk. He even recorded it several times to correct minor mistakes. I created Chinese subtitle for it and sent it to the OSPP organisers.

The students

The event went on well. We posted two student projects, one for migrating our JikesRVM binding to the new weak reference processing API, and another for supporting ARMv8. Several students expressed their interests in our Zulip channel, and some even asked for easy issues for beginners to fix so that they could get familiar with the MMTk project. Eventually, two students were selected by OSPP’s automated matching algorithm, and I mentored one of them to do the project related to JikesRVM and weak references.

Mr. Haohang Shi, the student I mentored, demonstrated his ability to learn things quickly. I simply told him to look at our continuous integration (CI) scripts, and told him that JikesRVM needs a 32-bit toolchain and an old version of JVM (version 8), and that I used LXC to make an isolate environment. In just one week or two, he managed to compile JikesRVM with the MMTk binding in a Docker container in one command. Haohang was surprised that I labelled such a simple project of implementing a new API as an ‘advanced’ task. The JikesRVM is an exotic meta-circular VM, with unconventional semantic extensions to Java in the form of VMMagic, and it interacts with native C and Rust code in unconventional ways different from the JNI which most Java programmers are familiar with. It is also a bit aged, requiring legacy toolchains, and is hard to debug when segmentation fault happens. All of these made his life harder than usual, but he fought through all those difficulties.

From then on, we had an online meeting every week. I basically point him to interesting places in the code base, outlining what should be done, and answering his questions.

Things went on mostly well, until Haohang got stuck trying to call a Rust closure from JikesRVM. I thought that was easy (but I was wrong). The crux was specialising a top-level function with type argument, and passing the pointer to the closure object between Rust and native code. We have similar code in our VM binding repos including the JikesRVM binding, because it is a common task for interfacing with native code. If this happens to my colleagues in the core team, I will just write part of the code for them should they encounter something difficult to implement. However, I didn’t do that for Haohang. One reason was that the rules of OSPP forbid mentors from doing coding for the students (otherwise some mentors would do everything for the student and the student would just sit there and do nothing and still get the bonus). Another reason was that I didn’t want to spoil all the fun of finding the solution by oneself. He eventually figured it out by himself after several weeks. That was a bit long, but he managed to finish the rest of the work before the deadline and his code was eventually merged.

In hindsight, I felt I might have been too harsh for Haohang. After he finished his project, a colleague in the MMTk team asked me a similar question about another binding. Then I realised it may not be so obvious for first-time contributors like Haohang.

Meanwhile, good news came from the other student working on the ARMv8 port. The student was able to run DaCapo Benchmarks on an ARMv8 device with MMTk and OpenJDK. In the end, both student projects were successful. We acknowledged their contributions on our website.

The bad

While the student projects went on well, the organisation of the OSPP’2023 event was far from perfect, and the experience as a participant was, to be honest, far from satisfactory.

The poorly engineered website

The official website was poorly engineered. It forced each user to have exactly one role. But since I am both a community representative and a student project mentor, I had to log in with two different email addresses for two different roles.

Although OSPP’2023 allowed communities to use Chinese or English or both, the website didn’t seem to be considerate enough for English users. The registration forms limit the length of some fields (such as the project description) by the number of characters, making them unfair for English which tend to have much more characters than Chinese. The typesetting was also weird. When breaking long lines, words can be broken anywhere, disregarding any hyphenation rules of the English language. Look at the following screenshot:

What is ‘Ope’ and what is ‘nJDK’? And it broke ‘support’ into ‘sup’ and ‘port’, and ‘minor’ into ‘mino’ and ‘r’.

It ended up that someone set the CSS property word-break: break-all;. I still don’t understand why anyone would do that, but I bet nobody tested the web page with a proper English article and, if anyone actually did, the tester was not aware of hyphenation rules. Anyway, I reported the issue to the organisers and they fixed it.

Where did they publish our video?

In the last section, I mentioned that we made an introduction video. Despite of the efforts we made creating it, I didn’t find the video published anywhere by OSPP’2023, and I didn’t get any reply saying whether our video was accepted or rejected.

They prefer WeChat, a proprietary instant messaging app

The official method for communicating with the organisers was via email. But when I sent an email asking questions, one organiser invited me to join a WeChat group. Despite its popularity in China, WeChat is a proprietary instant messaging application mainly focusing on smart phone, and is terrible to use on desktop computers. I felt very strange because OSPP stood for ‘Open Source Promotion Plan’. It was supposed to promote free open-source software. Why do they invite me to use a proprietary application?

But I joined the WeChat group anyway to see what would follow. That was a group titled ‘OSPP community collaboration’, and its members included 400+ representatives from different communities. People were asking questions and pointing out issues about the event, while the organisers replied.

They use proprietary storage service and proprietary image formats

After a few days, the organiser published a template pack for communities to make their promotional ‘posters’. Here is a sample:

For those who don’t know, those who use WeChat or other Chinese social media such as Weibo for promotion usually make such one-picture posters and publish them as tweets, or send them to group-chat channels. The advantage is obvious. It is just so simple, and it bypasses any text-formatting functionalities WeChat or other instant message / social media apps provide to their users, which are often hard to use.

The problem was, the organiser provided the template pack using a link to Baidu Wangpan, a Chinese cloud storage service that requires a proprietary client to use.

Seriously? Was OSPP trying to promote open-source software by forcing participants to use proprietary software? After complaining to the organisers of OSPP’2023, they moved the poster templates to a GitHub repository.

I browsed the repository. They provided the posters in two formats: a .sketch file and a .figma file. The former was for Sketch, a proprietary graphics software exclusive to Mac; and the latter was for Figma, a proprietary web-based graphics software. There were samples in .pdf and .jpg, too.

Are you kidding me? Providing open-source promotion material in two proprietary formats?

I complained to the organisers that there was absolutely no way for Linux users to open the .sketch file, and I don’t want to register a free account to use Figma with limited functionality, and I won’t buy a Mac just for OSPP. Even .psd could be slightly better because GIMP and Krita could open a subset of .psd files. An organiser replied in an embarrassed tone, saying that the artist who designed that poster was just asking them whether they should give the organisers the .psd file, too.

From the conversation, it was obvious that the OSPP organisers hired an artist to make a poster template for OSPP. The artist was probably an average artist who knew nothing about free open-source software, and the artist used their familiar tool, which happened to be Adobe Photoshop, to do their job. The organisers of OSPP probably assumed that community representatives were artists or other non-technical social media operators and probably used Mac, and exported the templates in Mac-friendly formats.

The Open-source Promotion Plan was not promoting open-source the right way

The organisers of OSPP were not organising an event for the free software community, but an average event whose theme happened to be about free software.

Using free software is such a basic thing for organising an event for the free software community. There are many free and open-source communication platforms, such as Zulip which MMTk is using, as well as the good old IRC and mailing lists. There are storage services accessible using only free software, such as their official website. And there is free graphics software, such as GIMP and Krita for bitmaps, and Inkscape for vector graphics.

And there are artists who are also free software lovers. The Krita community hosted interviews with artists who use Krita as their main creative tool. If you need help from artists who love free software, you can just ask, because the free software community is all about creation and sharing. The KDE community held a Plasma 6 Wallpaper Context, with requirements including ‘releasing under the CC-BY-SA-4.0 license’ and ‘creating the wallpaper in a non-proprietary format’. Many artists submitted their work, and the KDE community eventually got a good-looking new default wallpaper for KDE 6, as shown below (taken from their official announcement of the KDE 6 MegaRelease).

It was sad because it was so easy to do it right. Just export the image to the SVG format and all Linux users could edit the image using Inkscape. It should take a sophisticated artist less than ten minutes to do this, and a Linux user to test if it works by opening the SVG image with Inkscape. But they did not do it!

It was also sad because it had been three previous OSPP events and the organisers were still yet to understand the nature of the free software community. I wonder why nobody from the 400+ communities complained about similar issues before.

Organising a free software event this way sent a very bad message to the public that they didn’t really care about software freedom. Ironically, OpenEuler, a domestic Linux distribution, was a co-organiser of OSPP’2023. Using free image formats would have helped OpenEuler demonstrate that their operating system was suitable for everyday use, but they didn’t. I couldn’t help visualising an OpenEuler user going nuts when they couldn’t use their own operating system to open an image file from their own event.

In the end, we didn’t use their poster templates because a Markdown-formatted post in our Zulip channel was just enough for promotional purpose, and we didn’t have a social media account. I’d rather spend one afternoon fixing some bugs than trying to edit PDF or JPEG files directly, which would result in bad-looking images anyway. I raised an issue, asking the organisers to provide materials in free formats. However, at the time of writing, nobody had replied to that issue.

The ugly

Although the organisers of OSPP’2023 didn’t do a perfect job organising the event, they promised to do it better next time. I think there is still hope. Given enough time, OSPP will eventually be organised in the right way.

However, there was still one thing that could be worse — the communities. Not all communities, of course. Only a few of them.

An interesting fact was, although students were required to be enrolled in universities (not written on their official website, but I confirmed with the organisers), there was no such requirement for communities (any communities using OSI-approved open-source licenses would qualify). No offence to the people who didn’t go to university and still made excellent free software, such as Brian Fox who dropped out of high school and made the famous Bash shell. But that rule meant that you had to expect participating communities of any quality, from bleeding edge research projects from the China Academy of Science to hello-world projects made by first-time programmers, and their members to be any kind of people you may possibly meet in streets or psychiatric hospitals (I will elaborate, but no offence to the patients who are actually suffering from mental disorders).

They gave stars to each other’s repos

When I was invited into the WeChat group of 400+ community representatives, I found some members were greeting each other and offering to give stars to each other’s GitHub repositories. One of them ‘kindly’ asked if he could give a star to MMTk’s GitHub repository. I didn’t thank him, but I replied that he needed a five-star rating system for GitHub so that he could give one star to every repo he barely knew, and five stars to the repos he honestly loved.

I consider it cheating to blindly give stars to repositories of one’s ‘friends’ for boosting their ‘reputation’. That would make stars meaningless. In that way, a repo with lots of stars would mean many people genuinely liked it, or merely mean the author had many ‘friends’. I still prefer that stars mean the former.

They wanted everyone to know their software… err… sucks

While organisers and community representatives were using the WeChat group as a Q/A channel, several communities spammed the channel with news about every single point release of their software. Those posts became dominant since July when the programming phase started and very few questions were asked about administrivia. That was annoying.

Well, since they dared spamming, I dared challenging them.

They said they were faster than Spring…

I looked at one project. It advertised as a web framework, with Spring-like IoC container and annotation-based URL routing, but also supported GraalVM and claimed to be many times faster than Spring. Web, IoC and Graal. Didn’t that sound familiar? Yes. Micronaut. That is a Web framework, with Spring-like IoC container, annotation-based URL routing, and GraalVM support, too. I heard about Micronaut about four or five years ago, but this project seemed to be recently started, and poorly documented.

I asked its representative how his project was different from Micronaut.

‘The author of our project has never heard of Micronaut’, he answered, embarrassed, ‘If I have to find any difference, it’s that our project is made in China.’

Their official web site compared their framework against Spring all the time and claimed to be much faster, but never mentioned Micronaut at all. That was not good. You simply can’t claim your project is fast without comparing against the main contenders.

They said they were faster than Netty…

Then another project spammed, and I looked at that, too. It was a simple socket abstraction layer written in Java, similar to Netty, but poorly documented, and claimed to be twice as fast as Netty. I looked at the code for a moment and found something like this:

} catch (Exception e) {
    e.printStackTrace();
}

And in another function:

try {
    someNetworkOperation(...);
} catch (Throwable e) {
    setState(...);
    someNetworkOperation(...); // Exception thrown on this line won't be caught.
} finally {
    handleNetworkOperationResult(...); // Hey! The network operation may have failed!
}

That didn’t look very professional, did it? Anyone who has learned Java for a few months knows that e.printStackTrace() is not the right way to handle errors, and retrying a failed operation doesn’t guarantee that it will be successful the second time. Omitting all the error-handling code and running micro benchmarks that always succeed will always give you good numbers, but that’s meaningless.

I told its representative that they shouldn’t claim they were faster than Netty while they were not doing exception handling properly, just like MMTk can’t claim a GC algorithm to be faster while the write barrier was deliberately turned off. Otherwise people would challenge the result.

‘Our project has been challenged all along’, replied the project representative, ‘and I have long been used to it. Only those who used our project know how pleasant it is.’

Yuck! What an irresponsible developer!

But people were speaking for him!

Strangely, some other people in the WeChat group started to speak for him.

• One person said, ‘Some people want security while others want convenience. Everyone will get what they love.’
• Another person said, ‘As a low-level employee, I can’t care less about how users feel. Only the CTO needs to care about users, and we programmers only need to please ourselves.’

Seriously? I couldn’t believe what I saw. I asked whether they care about downstream projects built upon theirs (such as the ‘Chinese Micronaut’ mentioned earlier which happens to be its downstream project), and apparently they didn’t. Knowing this, I stopped arguing because that would be futile.

They hated free software and didn’t want to promote it

After I complained about OSPP’2023 not providing poster templates in free formats, the organisers said they will be more considerate the next time. However, other people in the WeChat group started whining.

• One person said in some fields, free software were far worse than their proprietary counterparts, therefore we (OSPP) may use proprietary software.
• Another person said it was good to practice the spirits of free software in this event, but we don’t need to force it.
• Another person said that OSPP gave me money and I should be satisfied and shut up.

But let’s look at the poster sample again.

Does it look good? Yes. It does. Well, it is good enough as a poster for an event like OSPP, but not that good. I still don’t quite like blue on blue, or white on light blue. It is not the case that it is so good, with all sorts of fancy effects, that it has to be drawn using best-of-breed tools like Adobe Photoshop. Could anyone create a poster of similar quality (or even better) using only free software? Given the result of the wallpaper contest, the answer is obviously yes. So the right question is not whether we should force using free software, but why not. OSPP stands open-source promotion plan, and the use of free software should be the default, the common sense, rather than something that needs to be ‘forced’.

They learned English for nine years and still couldn’t read simple English articles.

And when I shared the interviews with Krita artists, someone said he couldn’t understand those interviews because he didn’t speak English well.

Seriously? I started learning English since the fourth year in primary school, and nowadays Chinese schools start teaching English as a compulsory course since the third year. By the time when students finish high school, they will have been learning English for at least nine years (unless they were older than me and received worse education in their childhood). How could anyone learn English for such a long time and still can’t understand simple articles like those?

And they hated me.

And someone mentioned me in the group chat, telling me he bought a Mac, a very expensive model, for opening proprietary image formats. I started to realise that someone already started to hate me since I complained about all those proprietary formats and irresponsible developers.

I told him that he could have donated the money to support three students. He apparently broke down mentally, and started telling a pathetic story about himself, including dropping out of high school, joining an open-source organisation, and making 5000+ commits per year which most people don’t believe. Well, I believed what this poor guy said because he supplied a screenshot. But I felt sorry for his organisation because 5000+ commits per year means on average less than 20 minutes for each commit. You can achieve 5000+ commits per year, too, if you make 5000+ trivial changes that take less than 20 minutes to do, and the organisation enforces no code reviewing and no CI tests. You can’t do the same for the MMTk project because all pull requests need to be peer-reviewed and go through comprehensive CI tests which take about an hour, while performance-sensitive changes need to undergo performance evaluation on specially tuned testing machine which takes hours if not days.

Strangely, several other people started to sympathise with him.

• One said he didn’t have a high degree and had a hard time finding a job.
• Another said he only got 28 points (out of 150) in his English exam, and he could have gone to Peking University if he got 100 points or more.

And they swore to support each other.

How weird! I know dropping out of high school does not prevent Brian Fox from becoming a Hero in a Bash Shell, but I never expected I was surrounded by so many ‘heroes’.

A friend of mine

Later that year, a friend of mine visited me in Beijing after living overseas for many years.

He told me that many companies in China were simply copying the business models of companies overseas, but most of them had no idea what they were doing, and will bankrupt quickly. That meant if anyone or any company was doing honest research and development work, they will already be better than 90% of their peers in China.

Wait! That sounded horribly familiar! I told my friend about my experience in OSPP. I also mentioned a recent news about CEC-IDE (see this). CEC-IDE claimed to be an IDE fully original and fully made-in-China. But it ended up that they took the source code of Visual Studio Code, changed its name, added a login window for paid ‘VIP’ services, added some plug-ins, and labelled it as a home-brewed software, an ‘independently software developed by a state-owned corporation, with trustworthy quality’ (and it was close-sourced). Ironically, CEC-IDE was on the CCTV (China Central Television) News when it was released, not long before it became the laughing stock of all Chinese netizens.

It was said that the government already invested hundreds of millions of CNY into the project.

The whole story

Everything suddenly became clear. Here is the whole story, in four parts:

1. Since the trade war started, both Chinese companies and the Chinese government worried about their software supply chains.
2. They started pouring money into the field of domestic software and open-source software, thinking they could be the rescue.
3. Then some developers saw this as an opportunity. Since the consumers wanted domestic and open-source software, they just make domestic and open-source software for them.

Note that those developers don’t have to be FOSS lovers. Anyone who wants some quick money from investors may come, regardless of whether they like free software, whether they worked with free software projects before, or whether they use free software in their work. That explains why someone don’t care about whether we use free software in an open-source promotion plan. And those who speak for them were probably on the same boat.

But it is difficult to start from scratch, especially for those who have never been free software contributor. And here comes part four:

1. Instead, they simply copied existing open-source projects and label them as domestically developed.

Some copycats simply took the source code and changed the name. Other more sophisticated copycats wrote code from scratch, using existing open-source projects as frames of reference. Of course they didn’t care about the user, the documentation or the code quality. As long as it was made-in-China and/or open-source, investors would throw money into it, and average people (especially extreme nationalists) would hail it as the future star of China when they saw it on the news. And their bosses probably care more about the number of stars of their repositories because that would attract more eyeballs and probably more investment. And fluency in English was not required as long as they do everything domestically. In fact, some netizens (again especially extreme nationalists) have been advocating abolishing English education in China (although the Chinese education authorities strongly opposed), giving them yet another excuse to fail in their English exams.

Therefore, from time to time, we find Chinese open-source projects that are so similar to world-famous ones, but claim to be domestically developed.

The consequence

A ‘software supply chain’ built this way will be brittle, if working at all. High-level applications will be built on flawed low-level libraries which don’t even handle exceptions properly and may break at any time. But will low-level developers care? Probably not. The decision of which library to use would be way above their pay grade, and they would worry about their house rent and mortgage much more than software quality. Their bosses won’t worry about software quality, either, if their companies monopolise a field, for example, food ordering. When the end users have to choose between one faulty software and another because there are no other choices, all they can do is pressing the reload button and pray it would work the next time.

And will we win the trade war this way? Well, I won’t call it a win if average people are oppressed by faulty software instead of foreign countries.

What about English skills? Well, when they can’t fix their faulty software and realise they can’t read English, they will beg linguists to translate the README files of proper free software projects, while linguists ask them to wait in queue because they are busy translating README files for their rival companies. I’m sure the Chinese education authorities won’t let this happen.

Summary

OSPP’2023 was awesome.

Students were smart and passionate.

The organisers tried hard keeping the event running, but there were much room for improvement.

The communities? Most of them were honestly doing free software developments, while some people were completely jerks.

So should I tell people the Australian National University is awesome, and our research group is doing interesting researches? Yes, to the students, and probably most community members, too. In fact, some students already expressed their interests in studying in the ANU when I told them about this possibility.

What about those who can’t even read simple English articles and those who make bogus claims about their software performance? ‘They are not our target audience’, said one of my colleagues. The ANU does have English language requirements and severe punishment against academic dishonesty.

Rescue

Since CTRL+ALT+Fx didn’t work, I tried to log into my machine from another machine via SSH. It worked. I managed to get a shell, and restarted SDDM using sudo systemctl restart sddm. Then my computer became responsive again.

What was wrong?

Many things could go wrong. I updated quite some packages yesterday, and it was ArchLinux. As a rolling Linux distribution, any update could render the system unusable. But when I visited https://archlinux.org/, no recent news mentioned anything that needed manual intervention.

I was using NVidia’s open source driver (the nvidia-open package). Could that be a problem? I uninstalled that package and rebooted. It would still be frozen after logging in. So the display driver was not the problem.

I was using KDE Plasma Wayland session. Could that be a problem? I tried to start the session by typing startplasma-wayland on a TTY, and that started the session successfully for me. So Plasma Wayland may not be the problem.

I was using SDDM, the default display manager for KDE Plasma. Could that be a problem? I installed LXDM. LXDM could start the Plasma X11 session, but it was incapable of starting any Wayland sessions. I installed LightDM, but for some reasons it failed to start. I installed GDM. It could start the GNOME session, but it didn’t detect the presence of Plasma Wayland. In the end, I couldn’t find any display manager that could start the Plasma Wayland session besides SDDM. It could be SDDM’s problem, but I couldn’t confirm it.

I tried to created another user, and tried to log in and start the Plasma Wayland session via SDDM. Surprisingly, it worked. It gave my new user a desktop with default settings. This meant the problem was probably with my personal configuration.

What configuration?

I was using Fish as my default shell. I used chsh to change my default shell to Bash, and tried to log in. It worked. It logged into the Plasma Wayland session successfully. So it narrowed down the problem with my Fish configuration.

I moved my entire Fish configuration directory ~/.config/fish away, and attempted to login. It worked. That further confirmed that one (or more) of my Fish configuration file was wrong. Which one was it?

I tried to move my configuration files one by one from my backup location back to ~/.config/fish. It ended up that the file fish_variables was the culprit.

I then tried to gradually remove the lines from fish_variables. In the end, the culprit was the following line:

SETUVAR --export UID:1000

It is a universal variable. It means it could have been set at any moment in the past, and it persisted until today and caused the failure.

Solution

Removing the universal variable UID solved the problem, but I still don’t understand why that variable was set in the first place. And I don’t know why it was frozen when the UID environment variable was set. Actually I don’t know exactly what was frozen, the SDDM, or something in the Plasma Wayland session.

The anomaly

I made a pull request for MMTk-core. It sped up all benchmarks in the DaCapo Benchmarks suite, except the jython benchmark which became 3x slower in stop-the-world (STW) time (i.e. time spent doing garbage collection).

In the following plot, build3 is the baseline revision, build1 is an intermediate commit, and build2 contains my final change. The time is normalised to build3 for each benchmark.

I could conclude that the jython benchmark had some abnormal behaviour and the overall result (build2 in geomean) was still speeding up. But the 3x slow-down was too significant to overlook. I decided to investigate.

eBPF-based tracing and visualisation

Strangely, the slow-down was only observable on two of the testing machines in our laboratory. When I re-ran the jython benchmark with build1, build2 and build3 on my laptop, their stop-the-world (STW) times were similar. They were either equally good or equally bad. I guessed they were equally bad. I inferred that the problem was non-deterministic. It may be triggered under some unknown conditions.

The slow-down was in the STW time, which meant some GC activities became slower. But how would I know which GC activity was slow?

At that time, my colleagues were developing a eBPF-based tracing tool which can record the duration of each work packet during a GC, and visualise them on a timeline. Its overhead when not used was so low that we can leave the trace points in the code in release builds, and active them whenever we want to measure something. I thought it was the perfect tool for my task. Although the tool was still being developed, I asked my colleagues for a copy and gave it a try anyway.

The tool included a patch to the MMTk Core source code which inserted USDT (user statically-defined tracing) tracepoints at important places. They were compiled as NOP instructions, but could be patched at run time to execute custom code. I used the bpftrace command line utility to activate those tracepoints to record the start and the end of each work packet, then used a script to format the output into a JSON format which was then sent to Perfetto UI. Perfetto UI showed what happened during a GC in a timeline.

Actually, I observed two different timeline patterns from different GCs when running the jython benchmark.

The first pattern (I called it the ‘kind 1’ GC) looked like this:

This was a minor GC in a generational GC algorithm, and it was quite a typical one.

The green arrows in Thread 192576 marked the start of each stage.

• The Prepare stage happened before the green arrow near the ‘24.0792 s’ mark, during which there were many work packets named ScanXxxxRoot(s).
• The Closure stage happened between that green arrow and the next green arrow after the ‘24.0796 s’ mark, during which there were many green GenNurseryProcessEdges work packets.
• Then there were some short intermediate stages, such as FinalRefClosure which handled finalization.
• The Release stage happened near the end of the GC between the ‘24.0797 s’ and the ‘24.0798 s’ marks, where each worker executed some clean-up job.

Since a minor GC does not trace much objects (it only traces the nursery), the Closure stage did not took much time. A ‘kind 1’ GC typically takes only about 1 ms, despite the ScanStackRoot work packet in Thread 192587 and the GenNurseryProcessEdges packet in Thread 192581 being a bit too big due to an unrelated load-imbalance problem.

The second pattern (I called it the ‘kind 2’ GC) looked like this:

This was also a minor (nursery) GC, too, seen form packet name GenNurseryProcessEdges. The Prepare stage and the Closure stage are similar to the ‘kind 1’. (Please note the horizontal scale of the timeline. The Prepare and the Closure stages were in the far left of this plot, before the Finalization packet.) What was interesting was the FinalRefClosure stage where finalization were done. After the Finalization packet, lots of GenNurseryProcessEdges work packets were executed. It was obvious that finalization resurrected many objects. A ‘kind 2’ GC is significantly longer than a ‘kind 1’ GC. It may take more than 15 ms to execute.

Given that finalization is non-deterministic, we might infer that the slow-down was caused by an excessive amount of finalization due to non-deterministic execution. Problem solved…, or was it? I still needed to verify.

Printing out the GC times

I printed out the GC time of each GC in jython when running on a test machine in the lab.

With 1500M heap size, the GC time (i.e. STW time) of the original code (build3) and my modification (build2) were:

• Before: 2,2,1,8,1,2,9ms
• After: 1,21,1,10,1,20,9ms

So the GCs that took 21, 10, 20 and 9 ms should be doing finalization, right?

I ran it on another test machine (with identical hardware) with 1500M heap, too:

• Before: 2,1,1,11,1,3,8ms
• After: 2,27,1,9,2,25,8ms

The results were similar between two machines. I then tried to reduce the heap size.

When I reduce the heap size to 500M:

• Before: 1,1,1,1,1,2,2,1,1,5,9,2,2,1,2,1,1,2,1,2,1,5,8,4
• After: 1,1,1,1,1,30,1,1,1,4,8,1,1,1,1,1,1,27,1,1,1,3,8,4

When I reduce the heap size to 250M:

• Before: 1,1,2,2,2,1,1,2,1,1,2,1,3,1,2,2,1,1,1,1,2,4,5,6,4,1,1,2,1,1,2,1,1,1,2,2,1,2,2,2,2,2,1,1,1,1,1,2,1,1,4,7,5,4,2,2,
• After: 1,1,1,1,1,1,1,1,1,1,2,1,29,1,1,1,2,1,1,1,1,4,6,6,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,2,25,1,1,1,1,1,1,1,1,1,4,5,5,4,1,1,

If the slow-down were caused by excessive finalization, I would expect one build to have more GCs that had more than 15 ms of STW time. But it was not the case. Two builds had the same number of GCs, and the GC time of each pair of corresponding GCs were similar, too, except two pairs. No matter how large the heap size was, there were always exactly two GCs that took more than 20 ms in the ‘After’ case (i.e. build2, the build with my PR applied). For other GCs, most of them took 1 ms and I assumed they were the ‘kind 1’ GCs; some of them took 5 ms to 10 ms and I guessed they were the ‘kind 2’ GCs.

So the two 20+ ms GCs were interesting. What happened during them? Were they slow because of finalization, too?

I re-ran the test at 250M heap size on my laptop. Strange things happened.

• Before: 1,1,1,1,1,2,1,1,1,1,1,2,1,2,2,1,2,2,2,2,1,2,1,5,7,7,6,1,2,1,1,1,2,1,1,1,2,1,2,2,2,1,1,2,2,2,1,2,2,2,1,1,2,2,2,1,5,7,6,5,1,2,2,
• After: 2,1,1,1,1,1,1,1,2,1,1,1,2,2,2,1,2,2,2,2,1,1,1,7,8,7,5,1,1,2,1,1,1,1,1,1,2,2,1,1,1,2,1,2,2,2,1,1,1,1,1,1,1,1,1,4,6,6,6,4,1,1,

The mysterious 20 ms GCs vanished!

This meant those 20 ms GCs were definitely not ‘kind 2’ GCs because otherwise I would have observed them on my laptop.

This also meant I could not capture those mysterious 20 ms GCs on my laptop using eBPF tracing. I could only capture them on the lab machines.

Manual tracing

Since I could not use eBPF tracing on the lab machine due to lack of root access, I manually instrumented the code to log the starts and ends of each work packets. I printed the log in the same format as the output of the eBPF tool, used the same script to process the log into the JSON format, and fed the JSON into Perfetto UI. Then a nice timeline came out. (And you can try it by your self. Load this log file into https://www.ui.perfetto.dev/ and browse the timeline interactively.)

And that was a strange timeline, too. Why was the ProcessRegionModBuf work packet so large? The purpose of the ProcessRegionModBuf work packet is handling the write barriers for bulk accesses of arrays (such as System.arraycopy() in Java) between the last GC and this GC.

There might be two possibilities:

1. The jython benchmark did call System.arraycopy() on a very large array, therefore the work packet should exist in order to process the write barrier. However, it did not appear in the ‘Before’ build (build3) due to a bug.
2. The jython benchmark did not copy large arrays at all, but a bug (probably introduced or triggered by my PR) caused the write barrier to erroneously record an access to a large array while it did not, resulting in an abnormally large ProcessRegionModBuf work packet.

So which one was true?

Hacking the write barriers

I added a log at the place where a ProcessRegionModBuf work packet is created in order to see the sizes of the ProcessRegionModBuf work packets.

When running on the lab machines,

• in the ‘before’ build, all ProcessRegionModBuf work packets had lengths of 0;
• in the ‘after’ build, ProcessRegionModBuf came in all different sizes.

When running on my laptop, all ProcessRegionModBuf work packets had lengths of 0.

But it does not make sense to copy zero elements using System.arraycopy()!

Then I had reasons to believe that there was a bug in the write barrier code so that in the ‘before’ build, the write barrier failed to record any accessed array regions, making the GC erroneously faster than it should have been. In the ‘after’ build, the bug was not triggered, so the accessed array regions were recorded by write barriers as usual, resulting in a longer but actually normal STW time. In other words, it was not my PR that made the STW time longer, but the STW time had been shorter than it should have been.

One of my colleagues reminded me that there was an un-merged commit that fixes a bug in the write barrier code in the MMTK-OpenJDK binding. It was intended to fix an unrelated bug, but it was still worth giving it a try.

I cherry-picked that commit, and… Voila! It fixed the bug! The ‘before’ build then exhibited the two 20+ ms GCs, just like the ‘after’ build.

• Before: 1,2,2,1,1,29,1,1,2,5,8,2,1,1,1,2,1,29,1,1,1,4,9,3,

Conclusion

At this point, we could draw the conclusion. The STW time for the jython benchmark should have been 3x longer. However, due to the bug fixed by this commit, the barrier did not record the bulk accesses to arrays properly, and therefore did less things than it should have done. When I was running the DaCapo benchmarks at the beginning of this blog post, I set the heap size too large (1500M). With such a large heap size, GC was only triggered a few times, and the proportion of write barrier handling became more significant in STW time. Therefore the STW time for jython was only 1/3 of the normal time due to the missing write barrier handling.

However, my PR changed the behaviour in some way, and the bug was somehow not triggered when running on the test machines in the lab. And the sub-optimal implementation of the ProcessRegionModBuf work packet stuffed all the array slices delivered from barriers into one single vector, making it impossible to parallelise. It gave us a false impression that my PR made the jython benchmark 3x slower on the lab machines.

And due to non-determinism, the bug was still reproducible on my laptop with my PR applied. That was why I saw the 3x slow-down on the lab machines but not on my laptop.

What did I learn?

There is a saying that ‘One can not optimise things that one can not measure’. It is very true. I can hypothesise what caused the performance problem, but I can never be sure unless I verify it with experiment. In this example, I first thought the slow-down was just some random behaviour of the jython benchmark. I then thought the slow-down was due to excessive finalization. But experiments showed that the actual cause was a bug in the write barrier.

And the visualisation tool is a very useful one. It first showed me that some GCs took longer time due to finalisation, and it then showed me that there were even longer GCs due to buggy and sub-optimal write barrier handling. It is such a useful tool because with the timeline in front of me, I no longer need to guess what slowed things down. I just look at the timeline, and the work packet that becomes the bottleneck will stand out of the crowd. Since the eBPF-based tracing and visualisation tool was created, I have been using it to debug many performance issues in GC, including the execution of obj_free, various weak table processing tasks, and the load-balancing problems in the MMTk-Ruby binding.

For example, when I saw the following timeline, I knew the handling of obj_free was the bottleneck.

When I saw the following timeline (with manual annotation of which work packet created which), I knew the load balancing of the transitive closure stage needed to be improved.

And when I saw the following timeline, I knew the general load balancing was improved, but some objects took significantly longer to scan than other objects, and I should focus on those objects because they were the bottleneck.

The tool

I thank Claire Huang, Zixian Cai, and Prof. Steve Blackburn for creating such a useful tool.

The tool is now publicly available. The code has been merged into the master branch of mmtk-core. Related tools and documentation can be found in this directory.

The paper that describes this work is freely available online under the Creative Commons Attribution 4.0 International License, and will be presented in the MPLR 2023 conference.

Disclaimer: This is not part of the research of the MMTk project, and is not sponsored by the Australian National University or Shopify.

The first FPS game I played

When I was nine or ten years old, I played a PC game named “摇滚少林系列之七侠五义3D”, or “Rock’n’Shaolin: Legend of the Seven Paladins 3D” (abbreviated as “L7P” or “LSP”). That was the first first-person shooting (FPS) game I played. That was an unusual FPS game because of its Chinese Wuxia theme. Instead of using guns, the player fights using ancient Chinese weapons and “qigong”, a powerful martial art that launches fireballs at the enemies.

The game was released in 1990s and, like many games of that era, it ran on DOS. However, many games of that era (such as Doom and Duke Nukem 3D) also released the source code of their game engines so that developers could port the games to modern platforms. Such ports are called source ports. For example, zdoom is a port of Doom’s “id Tech 1” engine, and eduke32 is a port of Duke3D’s “Build” engine. Those ports allow us to play those 1990s games on modern GNU/Linux, MacOS, Windows, and many operating systems and hardwares you can imagine.

I wondered if there is a source port for the Legend of the Seven Paladins 3D, too. Fortunately, there is.

During Christmas last year, I found the BuildGDX project and many other projects developed by M210. BuildGDX is a port of the Build engine written in Java, and there are also ports of many Build engine games, such as DukeGDX for Duke Nukem 3D, WangGDX for Shadow Warrior, BloodGDX for Blood, and LSPGDX for L7P. It ended up that L7P was also built on the Build engine, and it was surprisingly the first game based on (an unreleased version of) the Build engine!

I cloned the repositories, converted the Eclipse projects to Idea projects, worked around some issues, and I managed to run it on my laptop, with ArchLinux and OpenJDK 19. Here is a screenshot. Note that LSPGDX changed the HUD a little bit to adapt to modern high-resolution displays. The game window was a bit small, though, because I hadn’t figured out how to change the window size by then.

Can it run with MMTk?

Since it ran on OpenJDK, an immediate question came to my mind: “Does it run with MMTk?” My colleagues and I have been actively maintaining mmtk-openjdk, the OpenJDK VM binding of MMTk. In version 10, OpenJDK refactored its GC framework and introduced a GC interface, making it easy to plug in new GC algorithms. Our MMTk binding implements that interface and allows OpenJDK to use any GC algorithms MMTk provides. It should be a drop-in replacement for its GC.

And it actually worked. After fixing some issues about soft references, LSPGDX ran on OpenJDK 11 with the MMTk binding.

Pay attention to the log output [... INFO mmtk::plan::global] User triggering collection. That was produced by MMTk core, and that meant the VM was actually using MMTk.

I gave it a 128MB heap. (That was way too generous. Back in the DOS era, that game ran with 4MB of total memory!) The game manually triggers a GC during start-up and another time when loading a saved game.

As the player walked in the corridors, it only triggered GC once every half minutes. The game lagged a little bit when GC happens, but was hardly noticeable.

However, when entering an area with a lot of enemies, like this one…

… it started to trigger GC once every several seconds. What was worse, every GC froze the game for about 3 seconds. Note the timestamp of the log messages “Triggering collection” and “End of GC” in the following screenshot.

I stopped the game because the frequent GC pauses made the game unplayable.

The GC algorithm I chose was Immix, a high-throughput but non-generational non-concurrent GC. There was a bug by then that prevented Generational Immix from running. But even if the GC was generational, once a full-heap GC happened, it would just take as long as this one.

This experiment showed that GC latency matters for game applications. And MMTk does have a concurrent GC algorithm. The concurrent LXR GC algorithm was published last year, but has not been merged into the mainline MMTk core, yet. I’ll probably try playing LSPGDX with MMTk again when LXR stablises.

My forks

Since then, I have been hacking BuildGDX and LSPGDX to fix bugs and enhance the gameplay. If you are interested, you can clone my repositories on GitLab.

• BuildGDX: https://gitlab.com/wks/BuildGDX
• LSPGDX: https://gitlab.com/wks/LSPGDX

Shopify generously sponsored the MMTk project to develop mmtk-ruby, a VM binding that enables Ruby to use MMTk as its garbage collector, and Chris has been the person actively working with us. Over the past few years, he has provided support for Angus Atkinson, the initial developer of mmtk-ruby, and me who continued the development of mmtk-ruby after Angus. Although we never met in person, I received great help from him during regular online meetings. He helped me getting familiar with the Ruby runtime with which I had no prior experience, and provided suggestions handling impedance mismatches between MMTk and Ruby. While I focused on getting MMTk to work, he helped with adding MMTk-related version flags, command-line options and other ergonomics. He fixed tests and set up a nightly build server. He helped identifying bugs in MMTk and its API. He also helped promoting our project, letting the community know our effort of improving Ruby with a powerful GC framework.

Sadly, Chris is no longer with us. It is a great loss for the MMTk project as well as the whole programming language and virtual machine community.

Note that this post alone may not be enough to teach you how to use coroutines in all those languages.

I’ll also provide basic information about coroutines, swap-stack, async/await, etc. in the appendices.

The task

Input:

• a nested list of numbers, such as [1, [[2, 3], [4, 5]], [6, 7, 8]]

Output:

• recursively output all numbers in the list. At each level, visit all numbers in one element before visiting any subsequent elements.

  When given the list above, the output should be 1, 2, 3, 4, 5, 6, 7 and 8, in that order.

Requirement:

• Use coroutine(s) to enumerate a nested list, and yield elements to the calling coroutine one at a time.

I will try to do this task using as many programming languages as possible, Rosetta Code style, to compare their coroutine syntax and API. At the time of writing (2022), different programming languages still differ greatly w.r.t. the design of coroutines.

The code

Ruby fibers (stackful, both asymmetric and symmetric)

Fibers are “primitives for implementing light weight cooperative concurrency in Ruby”.

Ruby fibers are stackful. According to the documentation:

As opposed to other stackless light weight concurrency models, each fiber comes with a stack. This enables the fiber to be paused from deeply nested function calls within the fiber block.

Ruby fibers can operate in both asymmetric and symmetric mode. I’ll demonstrate the task in both modes below.

Asymmetric

The Fiber#resume instance method resumes a fiber, and a subsequent call to the Fiber.yield class method jumps back to the resumer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def traverse(x)
  if x.is_a? Array
    x.each do |elem|
      traverse(elem)      # recursive call
    end
  else
    Fiber.yield x         # can yield within recursive calls
  end
end

def fiber_traverse(x)
  Fiber.new do
    traverse(x)
    raise StopIteration
  end
end

DATA = [1, [[2, 3], [4, 5]], [6, 7, 8]]

fiber = fiber_traverse DATA

loop do   # Break if StopIteration is raised.
  value = fiber.resume
  puts value
end

The Enumerator class can automatically transform block-based visiting functions into fiber-based coroutine. It uses fiber only when necessary. It uses fiber when used as external iterators (calling e.next explicitly), but still uses call-back for internal iteration (e.each { |v| ... }).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def traverse(x, &block)
  if x.is_a? Array
    x.each do |elem|
      traverse(elem, &block)
    end
  else
    block.yield(x)  # This is just a usual method call, not a coroutine yield.
  end
end

def enum_traverse(x)
  Enumerator.new do |yielder|   # The yielder encapsulates how to yield.
    traverse(x) do |value|
      yielder.yield(value)      # This may or may not use coroutine yield.
    end
  end
end

DATA = [1, [[2, 3], [4, 5]], [6, 7, 8]]

# We can do internal iteration
enum_traverse(DATA).each do |value|   # use call-back
  puts value
end

# and external iteration too.
e = enum_traverse(DATA)
loop do           # Break if StopIteration is raised.
  value = e.next  # This will use fiber.
  puts value
end

Symmetric

The Fiber#transfer method can switch to any fiber, but always needs an explicit fiber to switch to. We can pass the current fiber to the new fiber when we create it, so it can remember which fiber to transfer back to.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
require "fiber" 

def traverse(x, parent)
  if x.is_a? Array
    x.each do |elem|
      traverse(elem, parent)  # always remember the parent
    end
  else
    parent.transfer x
  end
end

def fiber_traverse(x)
  current = Fiber.current     # get the current fiber
  Fiber.new do
    traverse(x, current)      # pass the fiber as parent
    raise StopIteration
  end
end

DATA = [1, [[2, 3], [4, 5]], [6, 7, 8]]

fiber = fiber_traverse DATA
loop do   # Break if StopIteration is raised.
  value = fiber.transfer
  puts value
end

Lua threads (stackful, asymmetric)

Lua “threads” are stackful coroutines. Lua has a stackless interpreter, therefore it can easily implement stackful coroutines (Why? See appendix).

Lua provides asymmetric coroutines (with limitations) for the sake of simplicity and portability.

• Simplicity: According to Coroutines in Lua, asymmetric coroutines may be easier to understand.

  On the other hand, asymmetric coroutines truly behave like routines, in the sense that control is always transferred back to their callers. Since even novice programmers are familiar with the concept of a routine, control sequencing with asymmetric coroutines seems much simpler to manage and understand, besides allowing the development of more structured programs

• Portability: Supporting symmetric coroutines (or even proper stackful asymmetric coroutines) will require C to have coroutine facilities, such as swap-stack, which is not always available. According to Coroutines in Lua:

  Lua and C code can freely call each other; therefore, an application can create a chain of nested function calls wherein the languages are interleaved. Implementing a symmetric facility in this scenario imposes the preservation of C state when a Lua coroutine is suspended. This preservation is only possible if a coroutine facility is also provided for C; but a portable implementation of coroutines for C cannot be written.

  Lua also added a limitation: a coroutine cannot yield while there are C function frames on its stack. Otherwise, Lua would require a swap-stack mechanism for C, making Lua less portable.

In Lua, the coroutine.resume function continues the execution of a coroutine, and coroutine.yield jumps back to the calling coroutine.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function traverse(x)
  if type(x) == "table" then
    for i, v in ipairs(x) do
      traverse(v)         -- recursive call
    end
  else
    coroutine.yield(x)    -- can yield within recursive calls
  end
end

function coroutine_traverse(x)
  return coroutine.create(function()
    traverse(x)
    return nil
  end)
end

local list = {1, {{2, 3}, {4, 5}}, {6, 7, 8}}

local coro = coroutine_traverse(list)

while true do
  local _, value = coroutine.resume(coro)
  if value == nil then
    break   -- terminated
  end
  print(value)
end

The coroutine.wrap function can wrap the coroutine into an iterator function suitable for the generic for statement.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function traverse(x)
  if type(x) == "table" then
    for i, v in ipairs(x) do
      traverse(v)
    end
  else
    coroutine.yield(x)
  end
end

function coroutine_traverse(x)
  return coroutine.wrap(function()
    traverse(x)
  end)
end

local list = {1, {{2, 3}, {4, 5}}, {6, 7, 8}}

for value in coroutine_traverse(list) do
  print(value)
end

Python generators (stackless, asymmetric)

Python generators are a built-in feature since Python 2.x. They are single-frame coroutines.

A function that contains a yield keyword is considered a generator function. Calling a generator function will create a new generator object stopped at the beginning of the function, and can be resumed with the next(...) built-in function.

Being stackless, each coroutine has only one frame, so it cannot yield while calling another function. To implement recursive traversal with stackless coroutines, it is common to create one generator for each level of nested list, and yield values from the innermost coroutine to the outer coroutine, level by level.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def traverse(x):
    if isinstance(x, list):
        for elem in x:
            new_gen = traverse(elem)    # Create the next level of generator
            try:
                while True:
                    v = next(new_gen)
                    yield v             # Yield everything the inner generator yields
            except StopIteration:       # until iteration stops.
                pass
    else:
        yield x

DATA = [1, [[2, 3], [4, 5]], [6, 7, 8]]

gen = traverse(DATA)    # The top-level generator
try:
    while True:
        v = next(gen)   # Iterate through it
        print(v)
except StopIteration:   # until iteration stops.
    pass

Python’s for statement is a syntax sugar for calling next(...) until the exception StopIteration is thrown. The yield from statement is a syntax sugar for yielding everything from another generator. Using all the syntax sugar, the code above will become the following:

1
2
3
4
5
6
7
8
9
10
11
def traverse(x):
    if isinstance(x, list):
        for elem in x:
            yield from traverse(elem)   # Use "yield from" to yield everything.
    else:
        yield x

DATA = [1, [[2, 3], [4, 5]], [6, 7, 8]]

for v in traverse(DATA):
    print(v)

Python coroutines (WTF?)

Python 3.5 attempts to introduce async/await-based asynchronous programming mechanisms, but it used the word “coroutine” to refer to functions annotated with the async keyword, like async def foo(...), which is confusing. Async functions may contain the new await expression, but its semantics is very vaguely defined as “suspend the execution of coroutine on an awaitable object”, whatever “on an awaitable object” means. That is in stark contrast to the highly detailed semantics of co_await expression in C++20 and the .await expression in Rust.

In the face of ambiguity, refuse the temptation to guess.

– Zen of Python

Because it is so confusing, I am not going to do the task using Python “coroutines”.

Python greenlet (stackful, symmetric)

Symmetric

The greenlet library provides stackful symmetric coroutines.

Greenlets are stackful. According to the documentation:

A “greenlet” is a small independent pseudo-thread. Think about it as a small stack of frames; the outermost (bottom) frame is the initial function you called, and the innermost frame is the one in which the greenlet is currently paused.

Greenlets are symmetric. One greenlet can switch to another using the glet.switch() method to pass a value, or glet.throw() to switch and immediately raise an exception.

There are implementations of Greenlets for both CPython and PyPy.

The official greenlet implementation for CPython uses platform-specific assembly code (for amd64, aarch64, riscv, etc.) to switch native stacks, similar to what [Boost Context] does.

PyPy implements the greenlet API using stacklets, which are PyPy’s own swap-stack mechanism. Like [Boost Context] and the official greenlet for CPython, PyPy also uses platform-specific assembly code (for x86-64, aarch64, mips64, etc. Sorry, RISC-V.) to switch between stacks.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import greenlet

def traverse(x, parent):
    if isinstance(x, list):
        for elem in x:
            traverse(elem, parent)      # recursive call
    else:
        parent.switch(x)                # can switch at any level of stack
        
def greenlet_traverse(x):
    current = greenlet.getcurrent()     # remember the current coroutine
    def _traverse_x():
        traverse(x, current)            # and pass it as the parent
        current.throw(StopIteration)
    return greenlet.greenlet(_traverse_x)

DATA = [1, [[2, 3], [4, 5]], [6, 7, 8]]

glet = greenlet_traverse(DATA)
try:
    while True:
        v = glet.switch()   # switch to the greenlet
        print(v)
except StopIteration:
    pass

Emulate asymmetric coroutine using the parent field

We have just demonstrated that greenlets are symmetric. However, each greenlet has a parent. It is the coroutine to switch to when the current coroutine terminates, normally or by exception. However, it doesn’t mean greenlets are asymmetric because the parent can be changed at any time during execution, and it is not wrong to explicitly switch to the parent.

We can rewrite our last example and use the glet.parent field instead of our own parent variable to record the parent.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import greenlet

def traverse(x):
    if isinstance(x, list):
        for elem in x:
            traverse(elem)
    else:
        greenlet.getcurrent().parent.switch(x)  # switch to parent
        
def greenlet_traverse(x):
    def _traverse_x():
        traverse(x)
        raise StopIteration()
    return greenlet.greenlet(_traverse_x)  # The parent is the current greenlet

DATA = [1, [[2, 3], [4, 5]], [6, 7, 8]]

glet = greenlet_traverse(DATA)
try:
    while True:
        v = glet.switch()   # switch to the greenlet
        print(v)
except StopIteration:
    pass

JavaScript generators (stackless, asymmetric)

The function* declaration defines a generator function. Generator functions can have yield operator that pauses the execution of the coroutine.

When a generator function called, it creates a generator object. It can be used like an iterator. The next method switches to the coroutine.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function* traverse(x) {
    if (Array.isArray(x)) {
        for (const elem of x) {
            for (const y of traverse(elem)) {
                yield y;  // Yield what the inner layer yields.
            }
        }
    } else {
        yield x;
    }
}

const DATA = [1, [[2, 3], [4, 5]], [6, 7, 8]];

let gen = traverse(DATA);
for (;;) {
    const result = gen.next();  // Resumes the coroutine.
    if (result.done) {
        break;
    }
    console.log(result.value);
}

And there are syntax sugars. The yield* operator yields everything from another generator. Because a generator behaves like an iterator, the for-of statement can iterate through the values it yields.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function* traverse(x) {
    if (Array.isArray(x)) {
        for (const elem of x) {
            yield* traverse(elem)
        }
    } else {
        yield x
    }
}

const DATA = [1, [[2, 3], [4, 5]], [6, 7, 8]]

for (const v of traverse(DATA)) {
    console.log(v);
}

JavaScript async/await (stackless, asymmetric, asynchronous)

JavaScript provides asynchronous programming facilities in the form of async/await (see appendix). An async function always returns a Promise object which can be settled (fulfilled or rejected) later. An async function may contain await operators which cause async function execution to pause until its operand (a Promise) is settled, and resume execution after fulfilment.

Asynchronous programming is more like cooperative multi-tasking than coroutines.

Despite the difference, I now give an example of traversing nested lists using async/await. I create two concurrent tasks, one traverses the nested list, and the other prints the numbers, and they communicate through a “zero-capacity queue”. It is similar to multi-thread programming, except there is only one thread executing both tasks in alternation, and the execution is scheduled by a scheduler.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
// A zero-capacity queue.
// `enqueue` will block until another task calls `dequeue`,
// and `dequeue` will block until another task calls `enqueue`.
class ZeroQueue {
    constructor() {
        this.getter_resolver = null
        this.data = null
        this.setter_resolver = null
    }

    async enqueue(num) {
        if (this.getter_resolver != null) {
            // If a consumer came before, we satisfy it.
            this.getter_resolver(num)
            this.getter_resolver = null
        } else {
            // If we come first, we leave the value and wait until consumed.
            this.data = num
            await new Promise((resolve) => {
                this.setter_resolver = resolve
            })
        }
    }

    async dequeue() {
        if (this.setter_resolver != null) {
            // If a producer already came, we take the value and let it continue.
            this.setter_resolver(null)
            this.setter_resolver = null
            return this.data
        } else {
            // If we come first, we wait for the producer.
            return await new Promise((resolve) => {
                this.getter_resolver = resolve
            })
        }
    }
}

const queue = new ZeroQueue()

async function traverse(x) {
    if (Array.isArray(x)) {
        for (const elem of x) {
            await traverse(elem)
        }
    } else {
        // await may potentially yield,
        // giving the user an impression of block-waiting.
        await queue.enqueue(x)
    }
}

async function print_all() {
    for (;;) {
        // await may potentially yield,
        // giving the user an impression of block-waiting.
        const v = await queue.dequeue()
        if (v == "end") {
            return
        } else {
            console.log(v)
        }
    }
}

const DATA = [1, [[2, 3], [4, 5]], [6, 7, 8]]

// The first task traverses the list and signal termination.
traverse(DATA).then(() => {
    queue.enqueue("end")
})

// The second task keep polling till the end.
print_all()

JavaScript async generators (stackless, asymmetric, asynchronous)

Functions annotated with async function* defines an async generator function. An async generator is like a generator, but the .next() method returns a Promise so it can be awaited. This allows the generator to use await while iterating. It can also use the for await ... of statement as a syntax sugar.

This practice is like building coroutine on top of async/await on top of coroutine, which looks ugly to me. Anyway, here is the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
async function* traverse(x) {
    if (Array.isArray(x)) {
        for (const elem of x) {
            yield* await traverse(elem)
        }
    } else {
        yield x
    }
}

const DATA = [1, [[2, 3], [4, 5]], [6, 7, 8]]

async function main() {
    for await (const v of traverse(DATA)) {
        console.log(v);
    }
}

main()

Rust async/await (stackless, asymmetric, asynchronous)

Rust’s async and await keywords provides support for asynchronous programming (see appendix) based on stackless asymmetric coroutines. There is a dedicated book that covers asynchronous programming in Rust.

An async function or an async block, when executed, do not execute their bodies immediately, but creates an object that holds the execution context of that function or block. Each async function or block is represented to the user as a Future. The Future::poll method will resume the async thing until it yields (on an await site) or finishes.

The await expression can only be used in async functions or blocks. Its semantics is complicated but well-documented. It calls Future::poll on a Future object and, if the Future is ready, it grabs its value continues without yielding; otherwise, it yields from the current async function or block. When resumed, it will poll the Future again and may or may not yield depending on whether the Future is ready.

Implementation-wise, the documentation suggests that Rust decomposes an async function (or block) into a state machine (see appendix) where each state represents an await site.

Async/await is not supposed to be used like coroutines. In fact, the book Asynchronous Programming in Rust contrasts async/await against coroutines. I have given an example in JavaScript that traverses nested list using async/await using two tasks and a channel. It is possible to do the same in Rust, but that’ll need a scheduler. Since I am too lazy to write a scheduler or introduce a third-party scheduler, I’ll try a different approach here.

I’ll abuse the async/await mechanism to exploit its underlying coroutine and make it behave like a generator.

• Resume: We know that Future::poll resumes the coroutine. We call Future::poll directly, which is seldom done in usual async/await-based programs unless we are implementing the “executor” (i.e. scheduler).

• Yield: Each .await corresponds to a yield site. We customise the behaviour of our Future object (i.e. WaitUntilResultTaken) so that the .await always yields (Pending) when reached from within the coroutine, but will continue (Ready) when resumed from the main function. The behaviour is controlled by the result_taken variable.

The async fn traverse will recursively call itself in the .await expression, and will yield level by level through all the .await sites to the main function.

Then we have a problem. Whenever it yields, the value yielded to the .poll() call site in main is always Poll::Pending. Then how do we pass the traversed numbers to main? To work around this, the coroutine writes the number in a shared variable result_reporter.num before it yields. This makes the ResultReporter struct effectively behave like a “zero-capacity queue” in our previous example, but it connects the generator and the main function instead of two tasks.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
use async_recursion::async_recursion;
use std::future::Future;
use std::pin::Pin;
use std::sync::atomic::{AtomicBool, AtomicI32, Ordering};
use std::task::{Context, Poll};

#[derive(Default)]
struct ResultReporter {
    num: AtomicI32, // Rust is having problem figuring out whether the coroutine races with main,
    result_taken: AtomicBool, // so we just use atomic variables here.
}

impl ResultReporter {
    fn report_result<'a>(&'a self, num: i32) -> WaitUntilResultTaken<'a> {
        self.num.store(num, Ordering::Relaxed);
        self.result_taken.store(false, Ordering::Relaxed);
        WaitUntilResultTaken {
            result_taken: &self.result_taken,
        }
    }
    fn take_result(&self) -> i32 {
        let num = self.num.load(Ordering::Relaxed);
        self.result_taken.store(true, Ordering::Relaxed);
        num
    }
}

struct WaitUntilResultTaken<'a> {
    result_taken: &'a AtomicBool,
}

impl<'a> Future for WaitUntilResultTaken<'a> {
    type Output = ();

    fn poll(self: Pin<&mut Self>, _: &mut Context<'_>) -> Poll<Self::Output> {
        if self.result_taken.load(Ordering::Relaxed) {
            Poll::Ready(())
        } else {
            Poll::Pending
        }
    }
}

enum NestedList {
    Leaf(i32),
    Nested(Vec<NestedList>),
}

#[async_recursion]
async fn traverse(list: &NestedList, reporter: &ResultReporter) {
    match list {
        NestedList::Leaf(num) => {
            // This `await` expression will call `WaitUntilResultTaken::poll()` twice.
            // The first time is when we reach the `await` here.  It returns `Poll::Pending` so we yield.
            // The second time is when `main` calls `poll`.  It returns `Poll::Ready(())` so we continue.
            reporter.report_result(*num).await
        }
        NestedList::Nested(lists) => {
            for elem in lists {
                // This `await` will pass the `Poll::Pending` to the caller level by level until it reaches `main`.
                traverse(elem, reporter).await
            }
        }
    }
}

fn main() {
    // [1, [[2, 3], [4, 5]], [6, 7, 8]]
    let nested_list = NestedList::Nested(vec![
        NestedList::Leaf(1),
        NestedList::Nested(vec![
            NestedList::Nested(vec![NestedList::Leaf(2), NestedList::Leaf(3)]),
            NestedList::Nested(vec![NestedList::Leaf(4), NestedList::Leaf(5)]),
        ]),
        NestedList::Nested(vec![
            NestedList::Leaf(6),
            NestedList::Leaf(7),
            NestedList::Leaf(8),
        ]),
    ]);

    let result_reporter = ResultReporter::default();

    let mut coro = traverse(&nested_list, &result_reporter);

    let null_ctx = unsafe { &mut *std::ptr::null_mut::<Context>() };

    loop {
        let coro_p = unsafe { Pin::new_unchecked(&mut coro) };
        let poll_result = coro_p.poll(null_ctx); // Let the coroutine run.
        match poll_result {
            Poll::Pending => {
                // When pausing (at `await` sites) during execution, we get the result.
                let num = result_reporter.take_result();
                println!("{}", num);
            }
            Poll::Ready(()) => {
                // When finished, we just quit.
                break;
            }
        }
    }
}

Rust coroutine crate (stackful, asymmetric)

The third-part crate coroutine provides stackful asymmetric coroutines. It is built upon the context crate (see below).

It looks like this crate has not been maintained for quite some time and it won’t compile. I’ll not do the task using the coroutine crate. If you are interested, their documentation contains some examples.

Rust context crate (stackful, symmetric)

The third-part crate context is similar to [Boost Context]. It provides the abstraction of stackful symmetric coroutines.

It implements swap-stack using machine-specific assembly code (x86-64, AArch64, ppc64, sorry RISC-V).

The Context::resume method switches the thread to the other coroutine, and pass the context of the original coroutine so the thread can switch back.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
use context::stack::ProtectedFixedSizeStack;
use context::{Context, Transfer};

#[derive(Debug)]
enum NestedList {
    Leaf(i32),
    Nested(Vec<NestedList>),
}

fn traverse(list: &NestedList, t: &mut Option<Transfer>) {
    match list {
        NestedList::Leaf(num) => {
            // Context-switching consumes the `Context` object.  We have to take and replace it.
            let old_t = t.take().unwrap();
            let new_t = unsafe { old_t.context.resume(*num as usize) };
            *t = Some(new_t);
        }
        NestedList::Nested(lists) => {
            for elem in lists {
                // This is stackful coroutine.  We can do recursive function call.
                traverse(elem, t)
            }
        }
    }
}

fn main() {
    // [1, [[2, 3], [4, 5]], [6, 7, 8]]
    let nested_list = NestedList::Nested(vec![
        NestedList::Leaf(1),
        NestedList::Nested(vec![
            NestedList::Nested(vec![NestedList::Leaf(2), NestedList::Leaf(3)]),
            NestedList::Nested(vec![NestedList::Leaf(4), NestedList::Leaf(5)]),
        ]),
        NestedList::Nested(vec![
            NestedList::Leaf(6),
            NestedList::Leaf(7),
            NestedList::Leaf(8),
        ]),
    ]);

    extern "C" fn context_function(t: Transfer) -> ! {
        // The initial Transfer carries the pointer to the list as `data`.
        let list = unsafe { &*(t.data as *const NestedList) };

        // From now on, we'll frequently take and replace the Transfer. Use Option.
        let mut t_holder = Some(t);
        traverse(list, &mut t_holder);

        // Send a special value to indicate the end of traversal.
        let t = t_holder.unwrap();
        unsafe { t.context.resume(usize::MAX) };
        unreachable!();
    }

    let stack = ProtectedFixedSizeStack::default();

    let mut t = Transfer::new(unsafe { Context::new(&stack, context_function) }, 0);

    // The initial `resume` sends the list reference as a usize.
    t = unsafe { t.context.resume(&nested_list as *const NestedList as usize) };

    // Use this special value to indicate end of traversal.
    while t.data != usize::MAX {
        println!("{}", t.data);

        // Subsequent `resume` doesn't need to carry values.
        t = unsafe { t.context.resume(0usize) };
    }
}

C# iterators (stackless, asymmetric)

C# can implement iterators using the yield return or yield break statements. A function that contains yield returns an Enumerable<T> or Enumerator<T> which is resumed every time an item is requested.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
using System;
using System.Collections.Generic;

interface NestedList
{
    IEnumerable<int> Traverse();
}

class Leaf : NestedList
{
    private int num;

    public Leaf(int num)
    {
        this.num = num;
    }

    public IEnumerable<int> Traverse()
    {
        yield return num;
    }
}

class Branch : NestedList
{
    private List<NestedList> children;

    public Branch()
    {
        children = new List<NestedList>();
    }

    public Branch Add(NestedList child)
    {
        children.Add(child);
        return this;
    }

    public IEnumerable<int> Traverse()
    {
        foreach (var child in children)
        {
            // It is stackless.  We need to yield from the inner iterators.
            foreach (var y in child.Traverse())
            {
                yield return y;
            }
        }
    }
}

public class IteratorTraversal
{
    public static void Main()
    {
        // [1, [[2, 3], [4, 5]], [6, 7, 8]]
        var nestedList = new Branch()
            .Add(new Leaf(1))
            .Add(new Branch()
                    .Add(new Branch()
                        .Add(new Leaf(2))
                        .Add(new Leaf(3)))
                    .Add(new Branch()
                        .Add(new Leaf(4))
                        .Add(new Leaf(5))))
            .Add(new Branch()
                    .Add(new Leaf(6))
                    .Add(new Leaf(7))
                    .Add(new Leaf(8)));

        foreach (var n in nestedList.Traverse()) // Create the iterator
        {
            Console.WriteLine(n);
        }
    }
}

C# async/await (stackless, asymmetric, asynchronous)

C# supports asynchronous programming (see appendix). Like async/await in any other language, its programming model is more like cooperative multi-task programming than coroutines. It is possible to implement asynchronous traversal using an AsyncQueue to communicate between the traversal task and a consumer task that consumes the visited values. I am not going to give an example here.

C swapcontext (stackful, symmetric)

The C programming language itself doesn’t have any support for coroutines or swap-stack.

The POSIX function makecontext can create a “context” for a function on a given stack so that when a subsequent invocation of swapcontext swaps to that context, it will continue execution from the beginning of the given function on the given stack. This effectively provides a swap-stack mechanism, and can be used to implement symmetric coroutines.

One design flaw of makecontext is that it only supports passing int arguments to the given function. Because the size of int is platform-specific, it is hard to pass pointers across makecontext. According to the man page, POSIX 2008 removed makecontext and swapcontext, citing portability issues, and recommended the use of POSIX threads.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <ucontext.h>

struct Node {
    int value;
    struct Node *first_child;
    struct Node *next_sibling;
};

// [1, [[2, 3], [4, 5]], [6, 7, 8]]
struct Node node8        = { .value = 8,  .first_child = NULL,    .next_sibling = NULL      };
struct Node node7        = { .value = 7,  .first_child = NULL,    .next_sibling = &node8    };
struct Node node6        = { .value = 6,  .first_child = NULL,    .next_sibling = &node7    };
struct Node node678      = { .value = -1, .first_child = &node6,  .next_sibling = NULL      };
struct Node node5        = { .value = 5,  .first_child = NULL,    .next_sibling = NULL      };
struct Node node4        = { .value = 4,  .first_child = NULL,    .next_sibling = &node5    };
struct Node node45       = { .value = -1, .first_child = &node4,  .next_sibling = NULL      };
struct Node node3        = { .value = 3,  .first_child = NULL,    .next_sibling = NULL      };
struct Node node2        = { .value = 2,  .first_child = NULL,    .next_sibling = &node3    };
struct Node node23       = { .value = -1, .first_child = &node2,  .next_sibling = &node45   };
struct Node node2345     = { .value = -1, .first_child = &node23, .next_sibling = &node678  };
struct Node node1        = { .value = 1,  .first_child = NULL,    .next_sibling = &node2345 };
struct Node node12345678 = { .value = -1, .first_child = &node1,  .next_sibling = NULL      };

ucontext_t main_context;
ucontext_t coro_context;
int current_value;
bool finished;

void do_yield(int value) {
    current_value = value;
    swapcontext(&coro_context, &main_context);  // switch back to main
}

void visit_node(struct Node *node) {
    for (struct Node *current = node; current != NULL; current = current->next_sibling) {
        if (current->first_child == NULL) {
            do_yield(current->value);
        } else {
            visit_node(current->first_child);   // recursive call
        }
    }
}

void traverse() {
    finished = false;
    visit_node(&node12345678);
    finished = true;
}

int main() {
    getcontext(&coro_context);

    // Obviously, it is stackful.
    void *stack = malloc(65536);    // Not sure if 65536 is enough, though.
                                    // If we are careful enough, we should use mprotect
                                    // to create a PROT_NONE region to protect against
                                    // stack overflow.
    coro_context.uc_stack = (stack_t){ .ss_sp = stack, .ss_size = 4096 };
    coro_context.uc_link = &main_context;
    makecontext(&coro_context, (void(*)())traverse, 0);

    while (true) {
        swapcontext(&main_context, &coro_context);  // switch to coroutine
        if (finished) {
            break;
        } else {
            printf("%d\n", current_value);
        }
    }

    return 0;
}

C++ coroutine (stackless, asymmetric, asynchronous)

C++20 introduced “coroutines”. More precisely, it introduced mechanisms so that libraries can implement asynchronous programming on top of them.

Any function that contains co_await, co_yield and/or co_return are coroutine functions.

Calling a coroutine function behaves like the pseudo-code defined in Section 9.5.4 (dcl.fct.def.coroutine) paragraph 5.

{
    promise-type promise promise-constructor-arguments ;
    try {
        co_await promise.initial_suspend() ;
        function-body
    } catch ( ... ) {
        if (!initial-await-resume-called)
            throw ;
        promise.unhandled_exception() ;
    }
final-suspend :
    co_await promise.final_suspend() ;
}

Basically, it implicitly creates a “promise object” which is called (awaited) at different points of the coroutine execution, like “hooks” or aspect-oriented programming. The compiler will generate those promise.xxxx() method calls, and it is the programmer’s (or library writer’s) responsibility to define the “promise type” and the .initial_suspend(), .unhandled_exception(), and .final_suspend() methods to make the generated calls meaningful.

And evaluation a co_await expression behaves as defined in Section 7.6.2.3 (expr.await) paragraph 5. It takes an “awaiter” (more precisely, anything that can be converted to an “awaiter”) as operand, and

• It calls awaiter.await_ready().
  • If it returns true, it calls awaiter.await_resume(), and that’s the value of the co_await expression.
  • If it returns false, it calls awaiter.await_suspend(), and depending on its result, it may suspend the execution of the coroutine, or suspend and switch to another coroutine, or just continue execution.

It’s the “conditionally yielding” behaviour of common async/await-based programming. Again the compiler generates the above method calls, and it is again the programmer’s (or library writer’s) responsibility to implement the .await_ready(), .await_resume() and .await_suspend() methods to make those generated calls meaningful.

The co_yield expression calls promise.yield_value(x), and programmer (or library writer) shall implement the promise object to make .yield_value method meaningful.

And the co_return statement calls promise.return_void(), and the programmer (or library writer) shall implement the promise object to make .return_void method meaningful.

And the standard library function coroutine_handle::resume() resumes a paused “coroutine”.

As we can see

• the specification defines the semantics of coroutine functions, the co_await, co_yield and co_return expressions/statements, and the coroutine_handle library object and its .resume() method, and
• the compiler (GCC, Clang, etc.) generate code for the co_xxx expression/statements, and
• the programmer defines the promise type and (optionally) “awaiter” types and fills in lots and lots of methods to customise the behaviour.

How complicated C++20 “coroutines” are!

It is complicated enough to confuse a C++ programmer with 25-years’ experience.

And I admit I am not smart enough to use C++20 coroutines.

If you are not smart enough, either, but want to learn about C++20 coroutines, I recommend starting with another language, such as Ruby or Lua, and come back to C++20 when the idea of coroutines don’t scare you.

Anyway, here is the code. The following code tries to use C++20 coroutines as generators.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <iostream>
#include <coroutine>

struct Node {
    int value;
    Node *first_child;
    Node *next_sibling;
};

// [1, [[2, 3], [4, 5]], [6, 7, 8]]
Node node8        = { .value = 8,  .first_child = nullptr, .next_sibling = nullptr   };
Node node7        = { .value = 7,  .first_child = nullptr, .next_sibling = &node8    };
Node node6        = { .value = 6,  .first_child = nullptr, .next_sibling = &node7    };
Node node678      = { .value = -1, .first_child = &node6,  .next_sibling = nullptr   };
Node node5        = { .value = 5,  .first_child = nullptr, .next_sibling = nullptr   };
Node node4        = { .value = 4,  .first_child = nullptr, .next_sibling = &node5    };
Node node45       = { .value = -1, .first_child = &node4,  .next_sibling = nullptr   };
Node node3        = { .value = 3,  .first_child = nullptr, .next_sibling = nullptr   };
Node node2        = { .value = 2,  .first_child = nullptr, .next_sibling = &node3    };
Node node23       = { .value = -1, .first_child = &node2,  .next_sibling = &node45   };
Node node2345     = { .value = -1, .first_child = &node23, .next_sibling = &node678  };
Node node1        = { .value = 1,  .first_child = nullptr, .next_sibling = &node2345 };
Node node12345678 = { .value = -1, .first_child = &node1,  .next_sibling = nullptr   };

struct Traverser {
    struct promise_type;
    using handle_type = std::coroutine_handle<promise_type>;

    struct promise_type {
        int current_value_ = -1;
        bool finished_ = false;

        // This is executed when the "coroutine" is created.
        Traverser get_return_object() {
            return Traverser(handle_type::from_promise(*this));
        }

        // Called at the beginning of the coroutine.
        // We let it stop there to mimic Python generator behaviour.
        std::suspend_always initial_suspend() {
            return {};
        }

        // Called when the coroutine finished execution.
        std::suspend_always final_suspend() noexcept {
            // We set a variable so the main function knows it finished.
            finished_ = true;
            return {};
        }

        // Called when a co_yield expression is evaluated.
        std::suspend_always yield_value(int value) {
            current_value_ = value;
            return {};
        }

        // Called when an exception is thrown.
        void unhandled_exception() {
            std::terminate();
        }
    };

    handle_type handle_;

    Traverser(handle_type handle) : handle_(handle) {}

    void resume() {
        handle_.resume();
    }

    bool finished() const {
        return handle_.promise().finished_;
    }

    int get_value() {
        return handle_.promise().current_value_;
    }
};

Traverser visit_node(Node *node) {
    for (Node *current = node; current != nullptr; current = current->next_sibling) {
        if (current->first_child == nullptr) {
            // Yield.
            co_yield current->value;
        } else {
            // It is stackless.  We need multiple levels of coroutines.
            auto sub_traverser = visit_node(current->first_child);
            while (true) {
                sub_traverser.resume();
                if (sub_traverser.finished()) {
                    break;
                }
                // Yield from sub-coroutine.
                co_yield sub_traverser.get_value();
            }
        }
    }
}

int main() {
    auto traverser = visit_node(&node12345678);
    while (true) {
        traverser.resume();
        if (traverser.finished()) {
            break;
        }
        std::cout << traverser.get_value() << std::endl;
    }

    return 0;
}

C++ Boost.Coroutine2 (stackful, asymmetric)

Note: Boost.Coroutine is deprecated in favour for Boost.Coroutine2.

Boost.Coroutine2 provides stackful asymmetric coroutines. It is implemented on top of Boost.Context (see below).

A boost::coroutines2::coroutine<T> has two members: pull_type and push_type. A coroutine can be created by instantiating either of them. In this task, we will create a pull_type so that the main function can pull data from the coroutine. It will create a coroutine which receives a &push_type so that it can yield and push data back to the main function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <boost/coroutine2/coroutine.hpp>

struct Node {
    int value;
    Node *first_child;
    Node *next_sibling;
};

// [1, [[2, 3], [4, 5]], [6, 7, 8]]
Node node8        = { .value = 8,  .first_child = nullptr, .next_sibling = nullptr   };
Node node7        = { .value = 7,  .first_child = nullptr, .next_sibling = &node8    };
Node node6        = { .value = 6,  .first_child = nullptr, .next_sibling = &node7    };
Node node678      = { .value = -1, .first_child = &node6,  .next_sibling = nullptr   };
Node node5        = { .value = 5,  .first_child = nullptr, .next_sibling = nullptr   };
Node node4        = { .value = 4,  .first_child = nullptr, .next_sibling = &node5    };
Node node45       = { .value = -1, .first_child = &node4,  .next_sibling = nullptr   };
Node node3        = { .value = 3,  .first_child = nullptr, .next_sibling = nullptr   };
Node node2        = { .value = 2,  .first_child = nullptr, .next_sibling = &node3    };
Node node23       = { .value = -1, .first_child = &node2,  .next_sibling = &node45   };
Node node2345     = { .value = -1, .first_child = &node23, .next_sibling = &node678  };
Node node1        = { .value = 1,  .first_child = nullptr, .next_sibling = &node2345 };
Node node12345678 = { .value = -1, .first_child = &node1,  .next_sibling = nullptr   };

typedef boost::coroutines2::coroutine<int> coro_t;

void visit_node(Node *node, coro_t::push_type &sink) {
    for (Node *current = node; current != nullptr; current = current->next_sibling) {
        if (current->first_child == nullptr) {
            sink(current->value);   // Yield at any level.  It's stackful!
        } else {
            visit_node(current->first_child, sink);   // Recursive call.
        }
    }
}

int main() {
    auto traverser = coro_t::pull_type([](coro_t::push_type &sink) {
        visit_node(&node12345678, sink);
    });

    for (auto value : traverser) { // Can be used as iterator using begin() and end().
        std::cout << value << std::endl;
    }

    return 0;
}

C++ Boost.Context (stackful, symmetric)

Boost.Context implements a swap-stack mechanism using machine-dependent assembly language(x86-64, ARM64, RISCV64, etc.). We can also implement symmetric coroutines using its C++ API. A boost::coroutine::fiber represents a coroutine, and fiber::resume() switches to that coroutine. Because fiber::resume() doesn’t pass values, we need to use a side channel (the shared State object) to pass the value and indicate that the traversal has finished.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <boost/coroutine2/coroutine.hpp>

struct Node {
    int value;
    Node *first_child;
    Node *next_sibling;
};

// [1, [[2, 3], [4, 5]], [6, 7, 8]]
Node node8        = { .value = 8,  .first_child = nullptr, .next_sibling = nullptr   };
Node node7        = { .value = 7,  .first_child = nullptr, .next_sibling = &node8    };
Node node6        = { .value = 6,  .first_child = nullptr, .next_sibling = &node7    };
Node node678      = { .value = -1, .first_child = &node6,  .next_sibling = nullptr   };
Node node5        = { .value = 5,  .first_child = nullptr, .next_sibling = nullptr   };
Node node4        = { .value = 4,  .first_child = nullptr, .next_sibling = &node5    };
Node node45       = { .value = -1, .first_child = &node4,  .next_sibling = nullptr   };
Node node3        = { .value = 3,  .first_child = nullptr, .next_sibling = nullptr   };
Node node2        = { .value = 2,  .first_child = nullptr, .next_sibling = &node3    };
Node node23       = { .value = -1, .first_child = &node2,  .next_sibling = &node45   };
Node node2345     = { .value = -1, .first_child = &node23, .next_sibling = &node678  };
Node node1        = { .value = 1,  .first_child = nullptr, .next_sibling = &node2345 };
Node node12345678 = { .value = -1, .first_child = &node1,  .next_sibling = nullptr   };

struct State {
    int current_value = -1;
    bool finished = false;
};

void visit_node(Node *node, State &state, boost::context::fiber &sink) {
    for (Node *current = node; current != nullptr; current = current->next_sibling) {
        if (current->first_child == nullptr) {
            state.current_value = current->value;
            sink = std::move(sink).resume();   // Yield at any level.  It's stackful!
        } else {
            visit_node(current->first_child, state, sink);   // Recursive call.
        }
    }
}

int main() {
    State state;

    auto traverser = boost::context::fiber([&state](boost::context::fiber &&sink) {
        visit_node(&node12345678, state, sink);
        state.finished = true;
        return std::move(sink);
    });

    while (true) {
        traverser = std::move(traverser).resume();  // Resume the coroutine.
        if (state.finished) {
            break;
        }
        std::cout << state.current_value << std::endl;
    }

    return 0;
}

Appendices

Why this task?

The purpose of this task is to compare symmetric, asymmetric, stackful and stackless coroutines.

This task is natural to implement with coroutines, because the traversal of a data structure is relatively independent from the consumption of the values.

This task is also much easier with stackful coroutines than stackless coroutines. Because the data structure (nested lists) is recursive, it is easier to traverse it using a recursive algorithm, and recursion needs a stack. Stackful coroutines can handle recursive calls quite trivially. But when using stackless coroutines, we have to do some hack and chain up multiple coroutines to form a stack of coroutines, and yield values from the innermost coroutine through multiple layers of coroutines to the consumer.

From the code examples above, we can clearly see the difference between different kinds of coroutines.

What are coroutines anyway?

According to Conway, a coroutine is “an autonomous program which communicates with adjacent modules as if they were input or output subroutines”. Coroutines are subroutines all at the same level, each acting as if it were the master program when in fact there is no master program.

Coroutines has the following characteristics. (See Coroutines in Lua)

1. The values of data local to a coroutine persist between successive calls.
2. The execution of a coroutine is suspended as control leaves it, only to carry on where it left off when control re-enters the coroutine at some later stage.

The first characteristic means coroutines can be resumed from where it paused.

In the second characteristic, “as control leaves it” means it is the programmer that decides where to pause a coroutine, not the implicit scheduler. Control flow is part of a program, not the runtime.

For this reason, the “fibers” in Ruby, the “generators” in Python, the “threads” in Lua, and the “user contexts” in the swapcontext POSIX API are all coroutines, despite not being called “coroutines”. The programmer explicitly transfers control from one to another.

On the other hand, a “goroutine” in the Go programming language is not a coroutine, despite the similar name. In fact, the official document defines a “goroutine” as “an independent concurrent thread of control”, i.e. a thread.

Note: Goroutine is a threading mechanism implemented in the user space, an “M × N” green thread system. The Go runtime schedules M goroutines on N native threads. It is the scheduler that switches a native thread between different goroutines at unspecified time and locations, usually when IO operations may block, or when queues are full or empty. To the programmer, a goroutine is just like a thread: it keeps going forward. It may block, but not because the programmer asked it to yield, but because some requests cannot be satisfied, such as queues and IO.

Coroutines are not mutually exclusive with threads. Each thread is executing one coroutine at a time, and each thread may jump from one coroutine to another according to the control flow in the program.

Symmetric and asymmetric coroutines.

With symmetric coroutines, all coroutines are equal. A thread can jump from any coroutine to any other coroutine. When switching, the programmer always needs to specify which coroutine to jump to, i.e. destination.

With asymmetric coroutines, coroutines have a parent-child relation. There are two different operations that jumps between coroutines, namely resume and yield. When a thread “resumes” a coroutine, the destination becomes the child of the source coroutine, until it “yields”, when the thread jumps back from the child to the parent coroutine. A coroutine cannot be resumed when it already has a parent. When yielding, the programmer doesn’t need to specify the destination, because the destination is always implicitly the parent coroutine.

Symmetric and asymmetric coroutines have equal expressive power, and they can implement each other. See Coroutines in Lua for more details.

Stackful and stackless coroutines.

A stackful coroutine has its own execution stack. A thread can switch coroutine when the current coroutine has any number of frames on its stack. When switching, the thread saves the entire stack and switches to a whole new stack (implementation-wise, it only needs to save registers, change the stack pointer, and restore registers from the new stack).

A stackless coroutine has only one frame. Therefore, a coroutine is usually defined by a “coroutine function”. From my knowledge, all stackless coroutines are asymmetric. A coroutine function can only yield within the coroutine function itself. That means when a coroutine C1 calls another function F2, the thread cannot yield from C1 while executing F2; when a coroutine C1 resumes another coroutine C2, the thread can only yield from C2 back to C1, but not directly from C2 to C1’s parent.

Stackful coroutines are more powerful, but need some kind of “swap-stack” mechanism (see below) to implement. Stackless coroutines are more restricted, but does not require swap-stack.

The swap-stack mechanism

Conceptually, the context of nested function calls is a stack, a last-in-first-out data structure, called the control stack, often simply called a stack.

A control stack has many frames. Each frame contains the execution context of a function activation, (and this is why a frame is also known as an activation record). The context includes the program counter (PC) as well as the values of local variables. The top frame is the context of the most recently entered function, and is the only frame on a stack that is active. All other frames are paused at a call site, waiting for the called function (the frame above it) to return.

In most programming languages, a thread is always bound to one stack. But more generally, a thread can switch among different stacks. When a thread switches from one stack to another, it pauses the top frame as well making the whole stack paused. Then it switches its stack pointer to the new stack, and resume the top frame of the new stack, therefore continue from where that frame was paused.

This is basically what stackful coroutine does. Each coroutine has a stack, which can be paused and resumed. When resumed, it continues from where it was paused.

Implementing swap-stack with compiler

Implementation-wise, if the language is compiled, it needs a special instruction sequence that does the following things:

1. Save live registers on the top of the current stack, and
2. set the stack pointer (SP) register to the destination stack, and
3. restore the saved registers from the top of the destination stack.

The C and C++ programming languages themselves do not have support for swap-stack. In practice, we usually rely on libraries or compiler extensions to do that in C or C++.

Here I give two examples of implementations of swap-stack for compiled code.

1. One is from Boost.Context. It is implemented as a library in the assembly language, therefore it has to be platform-specific. Here are the code for x86-64, ARM64 and RISCV64. Because it is implemented as a library, it can only depend on the application binary interface (ABI) of the platform. In this case, the assembly code has to conservatively save all callee-saved registers no matter whether they are still in use or not, because as a library, it does not have the liveness information the compiler has.

2. The other is an LLVM extension created by Dolan et al.. As part of a compiler framework, it can identify and save only live registers, making it much more efficient than library-based approaches.

Implementing swap-stack with interpreter

If the language is interpreted, it depends. An interpreter can be stackful or stackless, and even stackless interpreters can allow the interpreted functions to call foreign C functions.

A stackful interpreter uses the native (C) stack to implement function invocation. Such interpreters usually has the following form:

void interpret_function(Frame *frame) {
    while (true) {
        switch (current_instruction().type()) {
        case ...:
            ...
        case CALL:
            ...
            Frame *new_frame = create_frame(called_function);
            interpret_function(new_frame);  // Recursive call
            ...
        }
    }
}

Because a language-level function call corresponds to an interpreter-level (C-level) function call, each frame in the interpreted language corresponds to a C frame. It is difficult to implement swap-stack with stackful interpreter because it needs to swap out the C stack (which has C frames) in order to swap out the interpreted language stack. As we have discussed before, C does not have native support for swap-stack, and it needs libraries written in assembly language or compiler extensions to do so.

What about stackless interpreters?

A stackless interpreter does not turn language-level function calls into C-level function calls. A stackless interpreter usually has the following form:

void interpret_function(Frame *initial_frame) {
    Frame *current_frame = initial_frame;
    while (true) {
        switch (current_instruction().type()) {
        case ...:
            ...
        case CALL:
            ...
            Frame *new_frame = create_frame(called_function);
            new_frame->parent = current_frame;
            current_frame = new_frame;  // Only replace the frame pointer
            ...
        }
    }
}

A stackless interpreter always remains in the single interpret_function function activation even when the interpreted language program makes a call. Swap-stack is relatively easier to implement with stackless interpreter, because it does not need to swap out any C frames…

… unless it allows foreign function calls. If the stackless interpreter allows the interpreted language to call foreign C functions, then C functions must have frames on some stack. Then we face the same problem as implementing swap-stack for compiled languages.

The Mu micro virtual machine

I designed the Mu micro virtual machine, and it is the main part of my PhD thesis. Swap-stack is a very important mechanism of the Mu micro VM, and it is designed to be supported by the JIT compiler. It enables the implementation of symmetric stackful coroutines, and it is the foundation of other VM mechanisms, such as trapping and on-stack replacement (OSR). If you are interested, read Section 5.3.6 of my thesis.

Decomposing a function into a state machine

Interpreters usually have no problem saving the frame of a function at a yield point so that it can be resumed later. The interpreter can implement the layout of stack frames and the behaviour of function calls / coroutine resumption in any way it wants. They may even allocate frames in the heap so that they can temporarily remove a frame from the stack and put it back later. For compilers, if swap-stack is available, one thread can just save the register states on one stack and restore them from another stack. Without swap-stack, however, it may be a challenge.

One way to implement pause-able and resume-able functions is decomposing a function into a state machine. Each yield point becomes a state, and a function starts by matching the state and jumping to the right place.

For example, assume the yield() call represents a coroutine yield in the following C pseudo-code:

void foo() {
    printf("Long\n");
    yield();
    printf("time\n");
    yield();
    printf("no\n");
    yield();
    printf("see\n");
    return;
}

Such a function can be transformed into a function that takes a state when called, and returns a new state when yielding or returning.

enum State {
    START, STATE1, STATE2, STATE3, END
};

enum State foo(enum State state) {
    switch(state) {
    case START:
        printf("Long\n");
        return STATE1;

    case STATE1:
        printf("time\n");
        return STATE2;

    case STATE2:
        printf("no\n");
        return STATE3;

    case STATE3:
        printf("see\n");
        return END;
    }
}

int main() {
    enum State state = START;
    while (state != END) {
        printf("Resuming foo()...\n");
        state = foo(state);
        printf("foo() paused\n");
    }
}

What about local variables? Local variables can be packed into the states, too. C programmers may use the union type, but it is easier with tagged unions or object-oriented programming.

Suppose we have a (pseudo) Rust function where yield!() represents a coroutine yield.

fn square_sum(a: i32, b: i32) -> Future<i32> {
    let a2 = a * a;
    println!("a * a = {}", a2);
    yield!();

    let b2 = b * b;
    println!("b * b = {}", b2);
    yield!();

    let result = a2 + b2;
    println!("result = {}", result);
    return result;
}

We can use an enum to hold live (will be used later) local variables at each yield!() point.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/// Note: each state holds the live local variables.
enum State {
    Start { a: i32, b: i32 },
    State1 { b: i32, a2: i32 },  // Note: a is no longer useful.
    State2 { a2: i32, b2: i32 }, // Note: neither a nor b are useful now.
    End { result: i32 },
}

/// Calling this function merely gets the initial state.
/// It doesn't actually execute the body of the original function.
fn square_sum(a: i32, b: i32) -> State {
    State::Start { a, b }
}

/// Call this for each step.
fn square_sum_step(state: State) -> State {
    match state {
        State::Start { a, b } => { // Restore local variables from the state.
            let a2 = a * a;
            println!("a * a = {}", a2);
            State::State1 { b, a2 } // Save useful local variables into state.
        }

        State::State1 { b, a2 } => { // restore
            let b2 = b * b;
            println!("b * b = {}", b2);
            State::State2 { a2, b2 } // save
        }

        State::State2 { a2, b2 } => { // restore
            let result = a2 + b2;
            println!("result = {}", result);
            State::End { result } // save
        }

        State::End { .. } => {
            panic!("Coroutine already finished!");
        }
    }
}

fn main() {
    let mut state = square_sum(3, 4);
    loop {
        match state {
            State::End { result } => {
                println!("Execution finished. Result is {}", result);
                break;
            }
            _ => {
                println!("Resuming...");
                state = square_sum_step(state);
                println!("Yielded.");
            }
        }
    }
}

Asynchronous programming (async/await) and coroutines

In asynchronous programming, a program consists of many tasks that can be completed in the future, and one task can wait for other tasks to complete before continuing. There are many ways to implement asynchronous programming. It can be trivially executed inline (e.g. the X10 compiler is allowed to inline an async activity), executed sequentially, using threads, or using coroutines.

The notion of “Future” and its friend “Promise” are well-known in multi-thread programming (C++, Java, C# and Python). A pair of Future and Promise represents a value yet to be produced. The Future waits for the value to be produced, and the Promise is a place to store the value to be acquired via the Future. C++ even has the std::async function in the standard library to launch an asynchronous task in a new thread.

Recently many programming languages employed a style of asynchronous programming language based on coroutines in the form of async/await. I guess the reason behind its gaining popularity is two fold:

1. Native, OS-provided threads are too heavy-weight, but not many programming languages support light-weight “M × N” green threads, that is, M OS threads are multiplexed to run N application-level threads and N ≫ M. AFAIK, only Erlang and Go supports such light-weight threads.

2. Not many languages support stackful coroutines. As we discussed before, stackful coroutines are only practical with swap-stack. Some languages (such as Kotlin) are targeted to runtimes (such as JVM) that don’t support swap-stack.

As a compromise, some languages resorted to coroutines. They attempted to implement cooperative multi-tasking using coroutines that yield when they are about to block, and a scheduler that decides which coroutine can continue without blocking. And there is async/await.

A function can be annotated with the async keyword. An async function is like a Python generator. When called, it doesn’t execute the body of the function immediately, but will create an object that holds the execution context of the function, like a frame. An async function may contain await expressions. An await is like a conditional yield. If a given Future is ready, then grab the value and continue; otherwise, suspend the execution and give control to the scheduler so that it can find something else to execute.

Async and await gives the programmer the feeling of multi-thread programming except that the programmer must explicitly annotate places that may potentially yield with await.

You can find an async/await example in JavaScript earlier in this post. It looks pretty like two threads communicating with each other using a channel.

Consequence of being stackless

Without proper swap-stack support, the compiler has to implement coroutines by decomposing async functions into state machines. await expressions are places the function may yield, and each await represents a state in the state machine.

However, async/await is not the only way to implement cooperative multi-task programming on top of coroutines. gevent is a Python framework based on Greenlets which implement symmetric coroutines. With the ability to switch coroutine at any level of stack, each coroutine can yield to the scheduler as part of potentially blocking functions (such as sleeping, IO operations, etc.), and programmers do not need to annotate any expression with await.

MMTk?

I have been contributing to the Memory Management Toolkit (MMTk) project since I left Huawei. MMTk is a framework for garbage collection. It was part of the JikesRVM, and has been a good platform for GC research. Many state-of-the-art garbage collection algorithms have been developed on it. Now we are re-implementing MMTk in Rust so that it can be integrated into many different languages and VMs, such as OpenJDK, V8, Julia, GHC, PyPy and, of course Ruby which I am working on.

As I started working on MMTk, one part of the code, that is, the TransitiveClosure interface/trait has always confused me.

TransitiveClosure?

In the core MMTk repository, the mmtk-core, you can find the TransitiveClosure trait and its implementation for all ProcessEdgesWork instances. (Let’s not worry about what ProcessEdgesWork does for now.)

pub trait TransitiveClosure {
    fn process_edge(&mut self, slot: Address);
    fn process_node(&mut self, object: ObjectReference);
}

impl<T: ProcessEdgesWork> TransitiveClosure for T {
    fn process_edge(&mut self, _slot: Address) {
        unreachable!();
    }
    #[inline]
    fn process_node(&mut self, object: ObjectReference) {
        ProcessEdgesWork::process_node(self, object);
    }
}

The presence of unreachable!(); startled me. The code implemented one method (process_node), but declared the other method (process_edge) unreachable. This is not how we usually use traits. When we define a trait with two methods, we expect both methods to be callable on all instances. Otherwise, why do we even have the process_edge method in TransitiveClosure in the first place?

I guess some types must have implemented the TransitiveClosure trait and provided a proper process_edge implementation. And… I am right. It is ObjectsClosure.

impl<'a, E: ProcessEdgesWork> TransitiveClosure for ObjectsClosure<'a, E> {
    #[inline(always)]
    fn process_edge(&mut self, slot: Address) {
        if self.buffer.is_empty() {
            self.buffer.reserve(E::CAPACITY);
        }
        self.buffer.push(slot);
        // ... more code omitted.
    }
    fn process_node(&mut self, _object: ObjectReference) {
        unreachable!()
    }
}

unreachable!() again? What the …!

Clearly ProcessEdgesWork and ObjectsClosure are implementing two different interfaces.

• ProcessEdgesWork only implements process_node, while
• ObjectsClosure only implements process_edge.

Should we split TransitiveClosure?

Maybe we should split it into two different traits, one contains process_node and the other contains process_edge. In this way, a type may only implement the trait it needs, and not the unreachable!() stub.

Or, should we?

To confirm this, let’s find their call sites, and see whether we ever use both methods at the same time. The short answer is, no.

The process_node method

process_node is only called by XxxSpace::trace_object, where XxxSpace is a concrete space. It can be CopySpace, MallocSpace, LargeObjectSpace and so on.

ImmixSpace even has two flavours of trace_object, both call process_node.

The trace_object method of a space visits an object during tracing. It marks or copies the object and, if it is the first time it visits an object, it enqueues the object into the marking queue by calling the process_node method which does the actual enqueuing.

The process_edge method

process_edge is only called by VM::Scanning::scan_object.

scan_object is implemented by a VM binding (such as the OpenJDK binding) because it is VM-specific. MMTk calls scan_object when it needs the VM to locate all reference fields in an object.

pub trait Scanning<VM: VMBinding> {
    fn scan_object<T: TransitiveClosure>(
        trace: &mut T,
        object: ObjectReference,
        tls: VMWorkerThread,
    );

    // ... more code omitted
}

The trait parameter is a call-back. When scan_object(trace, object, tls) is called, it scans object, and calls trace.process_edge on each edge, i.e. each reference field, of object.

Yes! They are different!

We confirmed that each of the two methods is used in a different scenario.

• process_node is only used by trace_object, and
• process_edge is only used by scan_object.

And nothing calls both process_node and process_edge at the same time.

So let’s split them into two traits.

But my colleague Yi Lin reminded me that there were other classes that extends TransitiveClosure in the original MMTk in JikesRVM. To be safe, I looked into the original JikesRVM MMTk before making further decisions.

Back in JikesRVM

Now we temporarily move away from Rust MMTk, and go back to JikesRVM MMTk. If the TransitiveClosure trait is designed like this in Rust, it must have its roots back in JikesRVM.

TransitiveClosure in JikesRVM MMTk

In JikesRVM, there is a class named TransitiveClosure. Yes. It is a class, not an interface.

@Uninterruptible
public abstract class TransitiveClosure {
  // Other methods omitted...

  public void processEdge(ObjectReference source, Address slot) {
    VM.assertions.fail("processEdge not implemented.");
  }

  public void processNode(ObjectReference object) {
    VM.assertions.fail("processNode not implemented.");
  }
}

Defining TransitiveClosure as a class allows it to provide failing default implementations of processEdge and processNode. This allows its subclasses to override one method while leaving the other failing.

(Note that the JikesRVM code was written before Java 8, so interface methods could not have default implementations.)

TransitiveClosure subclasses in JikesRVM MMTk

In JikesRVM, many classes inherit from TransitiveClosure.

• TransitiveClosure
  • TraceLocal
    • NoGCTraceLocal
    • MSTraceLocal
    • SSTraceLocal
    • MCMarkTraceLocal
    • MCForwardTraceLocal
    • ImmixTraceLocal
    • ImmixDefragTraceLocal
    • …
  • RCZero
  • RCModifiedProcessor
  • GenRCModifiedProcessor
  • ObjectReferenceBuffer
    • RCDecBuffer
  • TraceWriteBuffer

TraceLocal

Back in JikesRVM MMTk, there was no concept of “work packet”. The abstraction of tracing is the Trace class and its thread-local counterpart, TraceLocal. ThreadLocal was the local context of a GC thread during tracing GC.

public abstract class TraceLocal extends TransitiveClosure {
    @Override
    @Inline
    public final void processNode(ObjectReference object) {
        values.push(object);
    }

    @Override
    @Inline
    public final void processEdge(ObjectReference source, Address slot) {
        ObjectReference object = VM.activePlan.global().loadObjectReference(slot);
        ObjectReference newObject = traceObject(object, false);
        if (overwriteReferenceDuringTrace()) {
            VM.activePlan.global().storeObjectReference(slot, newObject);
        }
    }

    // ... more code omitted
}

In JikesRVM, TraceLocal is the counterpart of both ProcessEdgesWork and ObjectsClosure of the current Rust MMTk.

• Space.traceObject calls TraceLocal.processNode to enqueues newly visited objects,
  • just like XxxSpace::trace_object calling ProcessEdgesWork.process_node in Rust MMTk.
• Scanning.scanObject calls TraceLocal.processEdge to process each reference field (edge),
  • just like Scanning::scan_object calling ObjectsClosure.process_edge in Rust MMTk.

In JikesRVM MMTk, each plan (GC algorithm) defines its own TraceLocal subclass.

(Some GC algorithms. such as MarkCompact and Immix, even have more than one TraceLocal for different kinds of traces.)

It looks like the TransitiveClosure is a proper interface for TraceLocal. It implements both processNode and processEdge.

However, TraceLocal is the only class that implements both processNode and processEdge. Other classes don’t.

processEdge: Field visitors

Some subclasses of TransitiveClosure are related to reference counting (RC). They are RCZero, RCModifiedProcessor, etc. They only override the processEdge method, assuming processNode is never called.

What do they do?

They are field visitors. For example, RCZero visits edges and stores null to each field.

public final class RCZero extends TransitiveClosure {
    // Does not override processNode, leaving it failing

    public void processEdge(ObjectReference source, Address slot) {
        slot.store(ObjectReference.nullReference());
    }
}

During RC collection, RCZero is passed to Scanning.scanObject as the callback to set all reference fields of an object to null.

public abstract class RCBaseCollector extends StopTheWorldCollector {
    private final RCZero zero;  // This implements TransitiveClosure
    // ... more code omitted
    @Override
    public void collectionPhase(short phaseId, boolean primary) {
        // ... more code omitted
        if (phaseId == RCBase.PROCESS_DECBUFFER) {
            // ... more code omitted
            while (!(current = decBuffer.pop()).isNull()) {
                // ... more code omitted
                VM.scanning.scanObject(zero, current);  // Passing zero as callback
            }
        }
    }
}

Other RC-related classes are similar. They record the fields or apply decrements to the objects pointed by each field.

processNode: to enqueue objects

The TraceWriteBuffer class only implements processNode.

(In fact, TraceWriteBuffer is the only class that overrides processNode but note processEdge throughout the history of JikesRVM.)

public final class TraceWriteBuffer extends TransitiveClosure {
    private final WriteBuffer buffer;
    // ... more code omitted
    @Inline
    public void processNode(ObjectReference object) {
        buffer.insert(object.toAddress());
    }
}

TraceWriteBuffer is only used by CMSMutator (concurrent mark-sweep mutator).

public class CMSMutator extends ConcurrentMutator {
    private final TraceWriteBuffer remset;
    // ... more code omitted
    @Override
    protected void checkAndEnqueueReference(ObjectReference ref) {
        if (ref.isNull()) return;
        if (barrierActive) {
            if (!ref.isNull()) {
                if      (Space.isInSpace(CMS.MARK_SWEEP, ref)) CMS.msSpace.traceObject(remset, ref);            // here
                else if (Space.isInSpace(CMS.IMMORTAL,   ref)) CMS.immortalSpace.traceObject(remset, ref);      // here
                else if (Space.isInSpace(CMS.LOS,        ref)) CMS.loSpace.traceObject(remset, ref);            // here
                else if (Space.isInSpace(CMS.NON_MOVING, ref)) CMS.nonMovingSpace.traceObject(remset, ref);     // here
                else if (Space.isInSpace(CMS.SMALL_CODE, ref)) CMS.smallCodeSpace.traceObject(remset, ref);     // here
                else if (Space.isInSpace(CMS.LARGE_CODE, ref)) CMS.largeCodeSpace.traceObject(remset, ref);     // here
            }
        }
        // ... more code omitted
    }
}

In simple terms, the code above means “Trace the object ref in the space it is in, and, if it is the first time the object is traced, enqueue it in remset.”

What’s in common between TraceWriteBuffer and TraceLocal is that both of them contain a buffer (a remember set, or the tracing queue) where the traceObject method can enqueue newly visited objects to. This is what processNode is for, i.e. enqueuing objects.

So why not introducing a dedicated interface?

There comes an interesting question:

If some classes are just field visitors, why don’t we have a dedicated interface for it, and name it FieldVisitor?

and

If some classes are just places to enqueue objects, why don’t we have a dedicated interface for it, and name it ObjectBuffer?

TransitiveClosure has been there for 15 years. Many developers have made contributions to MMTk, and some of them must have noticed the issues I talked about. Why have TransitiveClosure remained this way till today?

And why did we end up having this TransitiveClosure amalgamation in the first place?

Through the history

To answer these questions, I dug into the Git revision history of the JikesRVM repository.

The git blame command can show me in which commit any line in any source file is last modified. I use vim-fugitive, and it even allows me to follow a line of code from one commit to another, and see every single change to a line of code in history.

Early days of object scanning

The history of Scanning.scanObject is the history of object scanning interface and implementation.

Back in 2003, MMTk (was JMTk back then) and JikesRVM were more tightly coupled than they are today. Unlike the modern Scanning interface, the ScanObject class back then contained concrete implementations directly. The ScanObject.scan method enumerates reference fields, and directly calls the Plan.traceObjectLocation static method, which does the load/traceObject/store sequence like our modern ProcessEdgesWork::process_edge method. Everything was hard-wired. The operation for visiting field was fixed.

A commit in 2003 introduced the ScanObject.enumeratePointers method which calls back to Plan.enumeratePointerLocation which can be customised. This allows a certain degree of freedom of what to do with each field, instead of load/traceObject/store.

Another commit in 2003 introduced the Enumerate class which was subsequently renamed to Enumerator and made fully abstract.

abstract public class Enumerator implements Uninterruptible {
    abstract public void enumeratePointerLocation(Address location);
}

The ScanObject.enumeratePointers method then used Enumerator as the call back instead calling into Plan directly, allowing the behavior of visiting each edge to be fully customised.

As I conjectured, some developers did notice that the call-back for scanObjects should be customisable, and Enumerator was introduced just for that.

In 2006, just before that important change

Both the Scanning.scanObject and Scanning.enumeratePointers existed in the Scanning class before late 2006.

public abstract class Scanning implements Constants, Uninterruptible {
    public abstract void scanObject(TraceLocal trace, ObjectReference object);
    public abstract void enumeratePointers(ObjectReference object, Enumerator e);
    // ... more code omitted
}

Both scanObject and enumeratePointers enumerate reference fields in an object. However, they are used in totally different places.

Scanning.scanObject

The Scanning.scanObject method was used for tracing, as it took TraceLocal as parameter, and called TraceLocal.traceObjectLocation for each reference filed.

Note that at that time, TraceLocal was a root class. There was no superclasses or interfaces like TransitiveClosure for it to extend/implement. (Constants is an all-static interface, and Uninterruptible is just a marker.) This means scanObject was only applicable to subclasses of TraceLocal, and nothing else.

public abstract class TraceLocal implements Constants, Uninterruptible { // no superclass
    public final void enqueue(ObjectReference object) throws InlinePragma { // traceObject calls this
        values.push(object);
    }
    
    public final void traceObjectLocation(Address objLoc, boolean root) // scanObject calls this
            throws InlinePragma {
        ObjectReference object = objLoc.loadObjectReference();
        ObjectReference newObject = traceObject(object, root);
        objLoc.store(newObject);
    }
    // ... more code omitted
}

Scanning.enumeratePointers

On the other hand, the Scanning.enumeratePointers could in theory be used by any code that needs to enumerate reference fields. At that time, it was used for (deferred) reference counting. The following was the “mark grey” operation in trial-deletion for cycle collection in reference counting.

public final class TrialDeletion extends CycleDetector
        implements Constants, Uninterruptible {
    private TDGreyEnumerator greyEnum;  // extends Enumerator
    // ... more code omitted
    private final boolean markGrey(ObjectReference object, long timeCap)
            throws InlinePragma {
        // ... more code omitted
        while (!object.isNull()) {
            // ... more code omitted
            if (!abort && !RefCountSpace.isGrey(object)) {
                RefCountSpace.makeGrey(object);
                Scan.enumeratePointers(object, greyEnum);  // pay attention to this call site
            }
            object = workQueue.pop();
        }
        return !abort;
    }
    // ... more code omitted
}

The call site of Scan.enumeratePointers passed a TDGreyEnumerator instance which customised the behaviour of visiting fields. It just forward the call to TrialDeletion.enumerateGrey.

public class TDGreyEnumerator extends Enumerator implements Uninterruptible {
    private TrialDeletion td;
    // ... more code omitted
    public void enumeratePointerLocation(Address objLoc) throws InlinePragma {
        td.enumerateGrey(objLoc.loadObjectReference());
    }
}

The obvious problem

We then had Scanning.scanObject for tracing, and Scanning.enumeratePointers for RC.

But why did we need both methods? scanObject was basically a special case of enumeratePointers that called TraceObject.enumeratePointerLocation.

Could we unify them? Apparently someone noticed that, and he did a refactoring.

Unifying scanObject and enumeratePointers with “TraceStep”

In late 2006, someone created a commit which introduced a new version of reference counting collector, and at the same time did “a huge refactoring” (see the commit message).

This commit created a class named TraceStep. Scanning.scanObject then took TraceStep as parameter instead of TraceLocal. The enumeratePointers method was removed.

public abstract class TraceStep implements Constants, Uninterruptible {
    public abstract void traceObjectLocation(Address objLoc);
}

public abstract class Scanning implements Constants, Uninterruptible {
    public abstract void scanObject(TraceStep trace, ObjectReference object);
}

Obviously, TraceStep was intended to replaced Enumerator as the call-back interface for scanObject to enumerating fields. Both tracing and RC started using scanObject from then on.

For tracing, the TraceLocal started to extend TraceStep.