Task backlog waiting times are power laws

Derek Jones from The Shape of Code

Once it has been agreed to implement new functionality, how long do the associated tasks have to wait in the to-do queue?

An analysis of the SiP task data finds that waiting time has a power law distribution, i.e., numTasks approx waitingTime^{-1}, where numTasks is the number of tasks waiting a given amount of time; the LSST:DM Sprint/Story-point/Story has the same distribution. Is this a coincidence, or does task waiting time always have this form?

Queueing theory analyses the properties of systems involving the arrival of tasks, one or more queues, and limited implementation resources.

A basic result of queueing theory is that task waiting time has an exponential distribution, i.e., not a power law. What software task implementation behavior is sufficiently different from basic queueing theory to cause its waiting time to have a power law?

As always, my first line of attack was to find data from other domains, hopefully with an accompanying analysis modelling the behavior. It’s possible that my two samples are just way outside the norm.

Eventually I found an analysis of the letter writing response time of Darwin, Einstein and Freud (my email asking for the data has not yet received a reply). Somebody writes to a famous scientist (the scientist has to be famous enough for people to want to create a collection of their papers and letters), the scientist decides to add this letter to the pile (i.e., queue) of letters to reply to, eventually a reply is written. What is the distribution of waiting times for replies? Yes, it’s a power law, but with an exponent of -1.5, rather than -1.

The change made to the basic queueing model is to assign priorities to tasks, and then choose the task with the highest priority (rather than a random task, or the one that has been waiting the longest). Provided the queue never becomes empty (i.e., there are always waiting tasks), the waiting time is a power law with exponent -1.5; this behavior is independent of queue length and distribution of priorities (simulations confirm this behavior).

However, the exponent for my software data, and other data, is not -1.5, it is -1. A 2008 paper by Albert-László Barabási ( detailed analysis)showed how a modification to the task selection process produces the desired exponent of -1. Each of the tasks currently in the queue is assigned a probability of selection, this probability is proportional to the priority of the corresponding task (i.e., the sum of the priorities/probabilities of all the tasks in the queue is assumed to be constant); task selection is weighted by this probability.

So we have a queueing model whose task waiting time is a power law with an exponent of -1. How well does this model map to software task selection behavior?

One apparent difference between the queueing model and waiting software tasks is that software tasks are assigned to a small number of priorities (e.g., Critical, Major, Minor), while each task in the model queue has a unique priority (otherwise a tie-break rule would have to be specified). In practice, I think that the developers involved do assign unique priorities to tasks.

Why wouldn’t a developer simply select what they consider to be the highest priority task to work on next?

Perhaps each developer does select what they consider to be the highest priority task, but different developers have different opinions about which task has the highest priority. The priority assigned to a task by different developers will have some probability distribution. If task priority assignment by developers is correlated, then the behavior is effectively the same as the queueing model, i.e., the probability component is supplied by different developers having different opinions and the correlation provides a clustering of priorities assigned to each task (i.e., not a uniform distribution).

If this mapping is correct, the task waiting time for a system implemented by one developer should have a power law exponent of -1.5, just like letter writing data.

The number of sprints that a story is assigned to, before being completely implemented, is a power law whose exponent varies around -3. An explanation of this behavior based on priority queues looks possible; we shall see…

The queueing models discussed above are a subset of the field known as bursty dynamics; see the review paper Bursty Human Dynamics for human behavior related aspects.

2-day More Concurrent Thinking class at CppCon 2022

Anthony Williams from Just Software Solutions Blog

I am excited to be going to CppCon again this year, where I will be running a 2-day class: More Concurrent Thinking in C++: Beyond the Basics.

The class is onsite at the conference venue in Aurora, Colorado, USA, on Saturday 10th September 2022 and Sunday 11th September 2022, immediately before the main conference.

I'll be teaching you to think about the synchronization properties of the constructs you use, and how to work with the low level facilities provided by the C++20 standard to build high level abstractions. We'll look at actors, thread pools and executors, and how to design code that works with those abstractions.

We'll look at how to use low-level atomic operations to build lock-free data structures, and the issues that can arise when doing so. We'll also look at how scalability concerns can impact your design choices.

Finally, we'll look at the important issue of testing multithreaded code, and the tools we can use to help us find the causes of problems.

If this sounds interesting, sign up for the class when you register for the main conference.

I'll also be doing a presentation on Tuesday: An Introduction to Multithreading in C++20. This is a whistle-stop tour of the multithreading features of C++20, briefly covering each feature and what it is used for, and which you should choose by default.

Whether you come to my class and presentation or not, I hope to see you there!

Posted by Anthony Williams
[/ news /] permanent link
Tags: , , ,
Stumble It! stumbleupon logo | Submit to Reddit reddit logo | Submit to DZone dzone logo

Comment on this post

Follow me on Twitter

Outreachy August 2022 update

Andy Balaam from Andy Balaam's Blog

I had the pleasure of being a mentor this summer for an Outreachy internship for the Matrix organisation. Outreachy provides internships to people subject to systemic bias and impacted by underrepresentation in the technical industry where they are living.

Outreachy is a fantastic organisation doing a brilliant job to try and make our sometimes terrible industry a little bit better.

Outreachy logo

Mentoring was great fun, mainly because it was such a pleasure working with my awesome intern Usman. There is lots of support available for interns and mentors through Outreachy’s Zulip chat (when will we persuade them to use Matrix? ;-) so you always have somewhere to turn if you have questions.

If you want to read more about the internship from Usman’s point of view, check out his blog posts:

  • Outreachy Blog – Introducing Myself
  • Wrap-up: Summary of my journey to being an outreachy intern at Element

    We talked every day on video calls, and really enjoyed working together. Some days we would just chat, sometimes I would give pointers for things to try in the code, or people to talk to. Some days we worked through some code together, and that was the most fun. Usman is incredibly enthusiastic and bright, so it was very satisfying making suggestions and seeing him put them into practice.

    Success!

    The work went very well, and Usman succeeded in creating a prototype that will help us design the Favourite Messages feature:

    Note: the feature isn’t ready to be fully release because it needs to be implemented on mobile platforms as well as changing where it stores its information: currently we use the browser’s local storage, but we plan to store things in Matrix, meaning it is automatically synchronised between devices.

    Things that went well

    • Meeting every day: we talked on a short video call every morning. This meant if we misunderstood each other it was quickly resolved, without lots of time being wasted.
    • Having a clear list of tasks: we kept a tracking issue on Github. This meant were clear what Usman was supposed to be doing now, and what was coming next.
    • Being flexible: we worked together to change the list of tasks every week or so. This meant we were being realistic about what could be achieved, and able to change in response to things we found out, or feedback from others.
    • Getting design input: we talked to Element’s designers several times during the project, showing them prototypes and early implementations. This meant we didn’t waste time implementing things that would need redesign later.
    • Support for me: I was able to work with Thib, who is our Outreachy Matrix community organiser, especially during the selection process. This meant I was not making decisions in isolation, and had support if anything tricky came up.
    • The Element Web community: Usman got loads of support from our community. Special thanks to Šimon, Olivier, Shay and t3chguy for your help!
    • Element the company: Element paid for this internship, and gave great support to Usman, integrating him into all our systems, inviting him to introductory meetings etc. He had every opportunity to see what working at Element is like, and to make an impression on everyone here. Element did a great job here.

    Things I would do differently

    • Managing the contribution period: before the project began, applicants are invited to contribute to the projects, allowing us to choose an intern based on those contributions. I felt slightly disorganised at this stage, and there was a lot of activity in issues and pull requests in the project from applicants. I think I should have warned our community and explained what was going to happen up-front, and maybe enlisted help from people willing to triage the contributions a little. Contributions varied in quality and understanding level, so having some volunteers who were primed to spend a little more time explaining and helping contributors get started would have prevented this impinging on the time of the team as a whole. Nevertheless, our team responded really well, and we got some useful contributions, and I hope the contributors had a good experience too.
    • Integrating Usman into the team: we chose a project that was independent from what other team members were doing, meaning he mostly interacted with others when he needed help. While it is sensible to make sure interns are decoupled from the main work (because it’s hard to predict how much progress they will make, and they are going stop after their internship), I do also wish we could have found a project that gave more opportunity to work with other people, not just “stealing” their time to help out, but actually working together on shared pieces of work. This is a tricky one to figure out, but food for thought.

    Conclusions

    The experience of being a mentor was really fun, and I would recommend it to anyone working on an open source project.

    I would emphasise, though, that you need to put aside enough time: the internship will not be successful if you don’t make time to work with your intern, get to know them, and introduce them to your community. Since interns may be new to the world of work, or shy about taking your time, as a mentor, you need to take responsibility for giving them enough support.

    Final note: as a mentor, you are NOT responsible for the work going well! Your responsibility is to help and support your intern, and give them everything they need to be successful (including feedback about things that are not working well), but it is up to the the intern themself to do the work, and how much work gets done is going to be the combination of a number of factors, including the intern’s experience and abilities. Don’t worry if you don’t get as far as you expected – after all, that happens in nearly all software projects…

Microsoft C++ versions explained

Anders Schau Knatten from C++ on a Friday

Microsoft has five different version numbers to think about when it comes to C++. Here’s an attempt to explain what they all mean.

  • Visual Studio release year (the “marketing version number”), e.g. Visual Studio 2022
  • Visual Studio actual version number, e.g. Visual Studio 17.0
  • Visual C++ (MSVC) version, e.g. MSVC 14.30
  • Toolset version, e.g. toolset 143
  • Compiler version, e.g. cl.exe 19.30

Visual Studio versions

What most people will see first is the Visual Studio release year. You’ll download Visual Studio 2022, Visual Studio 2019 etc. These however also have a more normal major.minor versioning scheme, and they bump the major version for every release year. So for instance VS 2017 is version 15, VS 2019 is version 16, and VS 2022 is version 17. Note that the year and the major version are not correlated in any way, except that Visual Studio 2010 just happened to also be version 10.

Visual Studio also has minor releases of each major version. Some examples (there are more minor releases per major than shown here):

Yearversion
Visual Studio 201715.0
15.3
Visual Studio 201916.0
16.1
Visual Studio 202217.0
17.1

source: Wikipedia

Visual C++ versions

Microsoft Visual C++, aka MSVC, ships as a part of Visual Studio, but has its own versioning scheme. Importantly, the major number signifies ABI compatibility, so something compiled with MSVC at one major version number can be linked against something compiled with any other MSVC at the same major version. (Some restrictions apply.) The MSVC major version number luckily gets bumped a lot less often than the Visual Studio version itself. As of Visual Studio 2015, they have kept the MSVC major version at 14. The first digit of the minor version seems to be bumped for each major version of Visual Studio itself. The Visual C++ version number is also used for the Visual C++ Redistributable.

Some examples:

VS YearVS versionMSVC version
Visual Studio 201715.014.1
15.314.11
Visual Studio 201916.014.20
16.114.21
Visual Studio 202217.014.30
17.114.31

source: Wikipedia

C++ toolset versions

Closely related to the MSVC version number is the C++ toolset version number. I can’t find a good source for it, but from Microsoft’s article it seems that the toolset version is made up of the MSVC major version and the first digit of the MSVC minor version. Some examples:

VS YearVS versionMSVC versionToolset version
Visual Studio 201715.014.1141
15.314.11141
Visual Studio 201916.014.20142
16.114.21142
Visual Studio 202217.014.30143
17.114.31143

Source: Microsoft

The linker (link.exe) also uses the C++ toolset version number as its version number, so e.g. for toolset 14.32 I might see link.exe version 14.32.31332.0.

Compiler versions

Finally, there’s the compiler version, which is what cl.exe reports. E.g. 19.16.27048. The major.minor version scheme correlates with the _MSC_VER macro which you can check in your source code (godbolt). So e.g. cl.exe version 19.21 has _MSC_VER 1921. (I’ll be nice and count those as one version number.)

VS YearVS versionMSVC versionToolset versionCompiler version
Visual Studio 201715.014.114119.10
15.314.1114119.11
Visual Studio 201916.014.2014219.20
16.114.2114219.21
Visual Studio 202217.014.3014319.30
17.114.3114319.31

The _MSC_VER version number is incremented monotonically at each Visual C++ toolset update, so if you want to only compile some stuff if the compiler is new enough, you can do e.g. #if _MSC_VER >= 1930.

Appendix: Running out of version numbers

Interestingly, the scheme where they bump the first digit of the Visual C++ minor version for each major release of Visual Studio means that they can only have nine minor versions of MSVC per Visual Studio major version! And looking at wikipedia, it seems they actually ran out of toolset versions at the end of Visual Studio 2019 and reused 14.28 and 14.29 for the final four Visual Studio 2019 releases (Visual Studio 16.8 and 16.9 had MSVC 14.28, Visual Studio 16.10 and 16.11 had MSVC 14.29).

Patterns in the LSST:DM Sprint/Story-point/Story ‘done’ issues

Derek Jones from The Shape of Code

Projects that use Scrum as their project management framework estimate tasks (known as a user story, or just story) in units of Story-points. A collection of User stories are grouped together to be implemented during a Sprint (a time-boxed interval, often lasting 2-weeks).

What are Story-points, and how do they map to time (in hours and minutes)? For this post, let’s ignore these questions, simply assuming that the people who assign a story-point value to a story have some mapping in their head.

What is the average number of story-points in a story, and how does this average vary across teams? What is the distribution of number of stories estimated per sprint, how many are actually implemented, and how does this vary across teams?

The data required to answer these questions has not been publicly available, or rather public data is not known to me. Until this week, I had only known of a few public Jira repos where story-points were given for at most a few hundred stories.

The LSST Corporation, a not-for-profit involved in astronomy and physics research, has a Data Management (DM) project. The Jira repo for this project contains 26,671 ‘Done’ issues (as of Aug 2022), of which 11,082 (41.5%) have assigned story-points; there have been 469 sprints, which involved 33% of the issues. The start/end implementation date/time for stories is mostly rather granular, and not fine enough to be used to attempt to correlate individual stories with hours. I found this repo, and a couple of others, via the paper Story points changes in agile iterative development, and downloaded all available issues.

What patterns are present in the story-point and sprint data?

Story points are commonly thought of as being integer valued, but 28% of the values are non-integer. If any developers are using the Fibonacci scale, there are not enough to have a noticeable impact. The plot below shows the number of stories estimated to involve a given number of story-points (black pluses are non-integer values, which have been rounded to fit the regression model). The green curved line is a fitted biexponential (sum of two exponentials), with the two straight lines being the two component exponentials (code+data):

Number of stories estimated to involve a given number of story-points.

One exponential is dominant for stories assigned up to 10 story-points, and the second exponential for higher story-point values.

The development team decides to implement a story and allocates it to a sprint. A story may be reallocated to another sprint before the start of the original sprint, or after the sprint is finished when its implementation is incomplete or not yet started (the data does not allow for these cases to be distinguished). How many sprints is a story allocated to, before the story implementation is complete?

The plot below shows the number of stories allocated to a given number of sprints, with a fitted regression line of the form Stories approx Sprints^{-2.8} (code+data):

Number of stories assigned to a given number of distinct sprints.

So around 14% of stories are allocated to two sprints, 5% to three and 2% to four.

How many stories are assigned to a sprint? The plot below shows the number of sprints having a given number of stories assigned to them, and the number of sprints implementing a given number of stories; lines are fitted loess models (code+data):

Number of sprints assigned a given number of stories, and implementing a given number of stories.

Are the Story/Story-point/Sprint patterns found in the DM project likely to occur in other projects using Scrum?

I don’t know, but I hope so. Developing theories of software development processes requires that there be consistent patterns of behavior.

Not knowing what stories were assigned to a sprint at the start of the sprint, rather assigned earlier and then moved to another sprint, potentially undermines the sprint patterns. We will have to wait and see.

If anybody knows of any public Jira repos where a high percentage (say 40%) of the issues have been assigned story-points, please let me know (all the ones I know of on the Atlassian site contain a tiny percentage of story-points).

Impact of number of files on number of review comments

Derek Jones from The Shape of Code

Code review is often discussed from the perspective of changes to a single file. In practice, code review often involves multiple files (or at least pull-based reviews do), which begs the question: Do people invest less effort reviewing files appearing later?

TLDR: The number of review comments decreases for successive files in the pull request; by around 16% per file.

The paper First Come First Served: The Impact of File Position on Code Review extracted and analysed 219,476 pull requests from 138 Java projects on Github. They also ran an experiment which asked subjects to review two files, each containing a seeded coding mistake. The paper is relatively short and omits a lot of details; I’m guessing this is due to the page limit of a conference paper.

The plot below shows the number of pull requests containing a given number of files. The colored lines indicate the total number of code review comments associated with a given pull request, with the red dots showing the 69% of pull requests that did not receive any review comments (code+data):

Number of pull requests containing a given number of files, for all pull requests, and those receiving at least 1, 2, 5, and 10 comments.

Many factors could influence the number of comments associated with a pull request; for instance, the number of people commenting, the amount of changed code, whether the code is a test case, and the number of files already reviewed (all items which happen to be present in the available data).

One factor for which information is not present in the data is social loafing, where people exert less effort when they are part of a larger group; or at least I did not find a way of easily estimating this factor.

The best model I could fit to all pull requests containing less than 10 files, and having a total of at least one comment, explained 36% of the variance present, which is not great, but something to talk about. There was a 16% decline in comments for successive files reviewed, test cases had 50% fewer comments, and there was some percentage increase with lines added; number of comments increased by a factor of 2.4 per additional commenter (is this due to importance of the file being reviewed, with importance being a metric not present in the data).

The model does not include information available in the data, such as file contents (e.g., Java, C++, configuration file, etc), and there may be correlated effects I have not taken into account. Consequently, I view the model as a rough guide.

Is the impact of file order on number of comments a side effect of some unrelated process? One way of showing a causal connection is to run an experiment.

The experiment run by the authors involved two files, each containing one seeded coding mistake. The 102 subjects were asked to review the two files, with file order randomly selected. The experiment looks well-structured and thought through (many are not), but the analysis of the results is confused.

The good news is that the seeded coding mistake in the first file was much more likely to be detected than the mistake in the second file, and years of Java programming experience also had an impact (appearing first had the same impact as three years of Java experience). The bad news is that the model (a random effect model using a logistic equation) explains almost none of the variance in the data, i.e., these effects are tiny compared to whatever other factors are involved; see code+data.

What other factors might be involved?

Most experiments show a learning effect, in that subject performance improves as they perform more tasks. Having subjects review many pairs of files would enable this effect to be taken into account. Also, reviewing multiple pairs would reduce the impact of random goings-on during the review process.

The identity of the seeded mistake did not have a significant impact on the model.

Review comments are an important issue which is amenable to practical experimental investigation. I hope that the researchers run more experiments on this issue.

Analysis of a subset of the Linux Counter data

Derek Jones from The Shape of Code

The Linux Counter project was started in 1993, with the aim of tracking the growth of Linux users (the kernel was first released two years earlier). Anybody could register any of their machines running Linux; a user ran a script that gathered basic information about a machine, and the output was emailed to the project. Once registered, users received an annual reminder to update information in their entry (despite using Linux since before the 1.0 release, user #46406 didn’t register until 2001).

When it closed (reopened/closed/coming back) it had 120K+ registered users. That’s a lot of information about computers, which unfortunately is not publicly available. I have not had any replies to my emails to those involved, asking for a copy that could be released in anonymized form.

This week I found 15,906 rows of what looks like a subset of the Linux counter data, most entries are post-2005. What did I learn from this data?

An obvious use is the pattern to check is changes over time. While the data does not include any explicit date, it does include the Kernel version, from which the earliest date can be inferred.

An earlier post used SPEC data to estimate the growth in installed memory over time; it has been doubling every 840 days, give or take. That data contains one data point per distinct vendor computer; the Linux counter data contains one entry per computer in use. There is around thirty pairs of entries for updated systems, i.e., a user updated the entry for an existing system.

The plot below shows memory installed in each registered computer, over time, for servers, laptops and workstations, with fitted regression lines. The memory size doubling times are: servers 4,000 days, laptops 2,000 days, and workstations 1,300 days (code+data):

Memory reported for system owned by Linux counter users, from 1995 to 2015.

A regression model using dates is a good fit in the statistical sense, but explain very little of the variance in the data. The actual date on which the memory size was selected may have been earlier (because the kernel has been updated to a later release), or later (because memory was added, but the kernel was not updated).

Why is the memory doubling time so long?

Has memory size now reached the big-enough boundary, do Linux counter users keep the same system for many years without upgrading, are Linux counter systems retired Windows boxes that have been repurposed (data on installed memory Windows boxes would answer this point)?

Suggestions welcome.

When memory capacity is limited, it may be useful to swap least recently used memory contents to disc; Linux setup includes the specification of a swap partition. What is the optimal size of the size partition? A common recommendation is: if memory is less than 2G swap size is twice memory; if between 2-8G swap size is the same as memory, and for greater than 8G, half of memory size. The table below shows the percentage of particular system classes having a given swap/memory ratio (rounding the list of ratios to contain one decimal digit produces a list of over 100 ratio values).

swap/memory   Server  Workstation   Laptop 
   1.0         15.2       19.9       25.9
   2.0         10.3        9.6        8.6
   0.5          9.5        7.7        8.4

The plot below shows memory against swap partition size, for the system classes laptop, server and workstation, with fitted regression line (code+data):

Memory and swap size reported for system owned by Linux counter users.

The available disk space also has a (small) impact on swap partition size; the following model explains 46% of the variance in the data: swapSize approx memory^{0.65}diskSpace^{0.08}.

I was hoping to confirm the rate of installed memory growth suggested by the SPEC data, with installed systems lagging a few years behind the latest releases. This Linux counter data tells a very different growth story. Perhaps pre-2005 data will tell another story (I just need to find it).

I’m not sure if the swap/memory ratio analysis is of any use to systems people. It was something of a fishing expedition on my part.

Other counting projects have included the Ubuntu counter project, and Hardware for Linux which is still active and goes back to August 2014.

I’m interested in hearing about the availability of any other Linux counter data, or data from other computer counting projects.

Transcoding video files for playback in a browser

Andy Balaam from Andy Balaam's Blog

ffmpeg -i original.mkv -c:v libx264 -c:a aac -ac 2 -ab 384000 -ar 48000 new.mp4

(Short answer: use the above ffmpeg command line. Read on for how I did this in Tdarr.)

I recently discovered Jellyfin, which gives me a Netflix-like UI for viewing my own videos, and seems great.

The only problem I had was that some videos were in formats that can’t be played natively in a web browser. Jellyfin heroically tries to transcode them on the fly, but my server is very lightweight, and there’s no way it can do that.

So, I needed to transcode those videos to a more suitable format.

Tdarr allows transcoding large numbers of files, and with a little head-scratching I worked out how to get it running, but I still needed the right ffmpeg options to make the videos work well in Firefox, without needing transcoding of video, audio or the container.

Here are the Tdarr settings that I found worked well:

Output file container: .mp4
Encoder: ffmpeg
CLI arguments: -c:v libx264 -c:a aac -ac 2 -ab 384000 -ar 48000
Only transcode videos in these codecs: hevc

Explanation:

  • Output file container: .mp4 – wraps the video up in an MP4 container – surprisingly, Firefox doesn’t seem to support MKV.
  • -c:v libx264 – re-encodes the video as H.264. Firefox can’t do H.265, and H.264 is reasonably compatible with lots of browsers. If you don’t care about Safari or various Microsoft browsers, you might want to think about VP9 as it’s natively supported on Firefox, so should work on weird architectures etc.
  • -c:a aac -ac 2 -ab 384000 -ar 48000 – re-encodes the audio as AAC with the right bitrates etc. Jellyfin was still transcoding the audio when I just specified -c:a aac, and it took me a while to work out that you need those other options too.
  • Only transcode videos in these codecs: hevchevc means H.265 encoding, and the videos I had problems with were in that encoding, but you might have different problems. If in doubt, you can choose “Don’t transcode videos in these codecs:” and uncheck all the encodings, meaning all your videos will be re-encoded.

If you are not using Tdarr, here is the plain command line to use with ffmpeg:

ffmpeg -i original.mkv -c:v libx264 -c:a aac -ac 2 -ab 384000 -ar 48000 new.mp4