Forem: Rohit Awate

My First Contribution to Firefox

Rohit Awate — Wed, 06 Nov 2019 17:43:49 +0000

Originally published on my personal blog.

Since the past couple of years, I've open-sourced most of my projects and also contributed to a few small ones. However, I've always wanted to contribute to a large, popular open-source project. I finally got around to doing that last month: I submitted a patch to Mozilla Firefox's JavaScript engine, SpiderMonkey, which was accepted on November 2.

I use Firefox every day. I appreciate and believe in the values and principles of privacy and an open Internet that Mozilla holds. Also, I have the highest amount of respect for people that volunteer in such projects. Thus, it felt great to contribute back!

This post serves two purposes:

to document my experience with the hopes of inspiring people to contribute to Mozilla (or other major open-source projects, for that matter)
to serve as a guide for someone making their first contribution to Mozilla since they have a pretty involved process and I don't want you to repeat the same mistakes as me!

Finding a Bug

My patch fixes this bug, which I found via Codetribute. You can use the 'good first bug' filter to find beginner-friendly bugs. Codetribute only lists bugs; they actually reside on Mozilla's bug tracker, BugZilla. Once you find a bug that you find interesting, check if someone else is already working on it. If not, add a comment that you wish to work on it.

You'll have to search for the instructions to get the source code, build the project, run tests and so on. For example, here's SpiderMonkey's getting started guide. This will vary depending on which project/module of Firefox you're contributing to.

The Bug I Fixed

My contribution improves the errors reported by the JavaScript parser. Luckily, I got to work on a brand-new feature of JavaScript called numeric separators. This allows you to make your long numeric literals more readable by adding underscores between digits. This feature just shipped in Firefox 70 in late October 2019 and my patch will be live in Firefox 72.

// Hard to read
let i = 1000000;

// Numeric separators improve readability
let i = 1_000_000;

The ES6 specification only allows a single underscore as a numeric separator between two digits. Additionally, a numeric literal must not end with an underscore. Thus, the following lines of code are illegal:

let i = 100__0;

let j = 100_;

If you run this code under Firefox 70, you'll see the same error in both cases:

Makes sense, right? However, the SpiderMonkey team wanted separate error messages for these cases. Following is a screenshot from Firefox Nightly, which includes my patch:

These error messages are contextually aware and more in line with what the programmer would expect.

Writing the Fix

Thankfully, Mozilla's Jason Orendorff had provided detailed instructions on the BugZilla thread regarding the fix. Hence, it was just a matter of a few lines of C++. It was really simple.

You can view the patch here.

If you have any doubts, just leave a comment on the BugZilla thread or reach out to the respective team on IRC. Mozilla's community is incredibly welcoming, helpful, smart and patient. Don't hesitate to ask questions. Communication is key. That's one of the most important things I learned in this process.

Creating a Patch

Once you've made the changes, run the tests and are ready to submit, you can commit to the local Mercurial repository:

// view the changed files
hg status

// view your changes
hg diff

// stage all of your changes
hg add .

// commit the staged changes
hg commit -m "Bug 1589072 - Improve numeric separators error messages"

For the commit message, use the above format. That number is the ID of the bug and the following message is its title, both from BugZilla.

Submitting the Patch

This is the tough part and where I messed up the most. Mozilla uses it's own infrastructure and thus it's not as easy as opening a Pull Request on GitHub.

First, you need to submit your patch for review. Mozilla uses Phabricator for this purpose. In order to submit your patch there, you need to use a command-line tool called moz-phab. Follow this guide for setting up your Phabricator account and to install moz-phab locally.

Next, open a terminal and cd into the Firefox repository. Here, you can simply run moz-phab and it will push your changes to Phabricator and create a revision. The link to it will appear in your terminal.

For more information about using Phabricator, check out this workflow walkthrough.

Code Review

Now, you need to wait for someone from the team to review your patch. They might request some changes or make some suggestions. Make the necessary changes. Again, if you have any doubts or questions, communicate with the team and get them cleared!

Submitting Changes to your Patch

This is where you need to exercise caution. You might assume that you just need to run hg commit and moz-phab again to push your changes to Phabricator. If you do this, you'll end up creating a completely new revision on Phabricator. This is the mistake I made.

You shouldn't create a new commit. Instead, add the changes to your original commit. You can do this using:

hg commit --amend

Don't add the -m flag. Just run the above command, which will open your text editor asking you for a commit message. Add that; it can be the same as before. On the following lines, add this:

Differential revision: <link-to-original-phabricator-revision>

// for example:
Differential revision: https://phabricator.services.mozilla.com/D51134

This tells moz-phab that this commit is a revision to your original patch. Consequently, it adds these changes to the same revision. You will be able to see your revision on Phabricator now.

Acceptance and Landing

If the reviewer is satisfied with your changes, s/he will accept your patch. Next, you need to wait for someone to 'land' your patch. I'm not entirely sure but I think that means committing your patch to the central repository. One of Mozilla's sheriffs will do that for you since you most likely don't have commit rights if you're reading this post.

Once that's done, well, congratulations! Not only did you work through your first patch and submit it, but you also got it accepted! You can check out your change live in the Firefox Nightly build.

Conclusion

I hope this post served one of its goals (or maybe both): either inspiring or helping you. I enjoyed this process and am proud of my patch, however little and simple it was. I hope to contribute regularly to Firefox henceforth.

We use open-source software every day, knowingly or not. If you have the time and skills, please contribute! The feeling of giving back is amazing.

That's it for today, see you in the next one!

PS: I would like to thank my friend, Jaydeep Borkar, whose contribution to spaCy inspired me to do this!

Demystifying Tail Call Optimization

Rohit Awate — Thu, 11 Jul 2019 16:09:52 +0000

Originally published on my personal blog.

Tail call optimization (a.k.a. tail call elimination) is a technique used by language implementers to improve the recursive performance of your programs. It is a clever little trick that eliminates the memory overhead of recursion. In this post, we'll talk about how recursion is implemented under the hood, what tail recursion is and how it provides a chance for some serious optimization.

Recursion 101

If you're familiar with function call stacks and recursion, feel free to skip this section.

Most languages use a stack to keep track of function calls. Let's take a very simple example: a "hello, world" program in C.

#include <stdio.h>

int main()
{
    printf("hello, world!\n");
    return 0;
}

Every function call in your program gets its own frame pushed onto the stack. This frame contains the local data of that call. When you execute the above program, the main function would be the first frame on the stack, since that's where your program begins execution. The topmost frame in the stack is the one currently being executed. After it completes execution, it is popped from the stack and the bottom frame resumes execution.

In our example, main in turn calls printf, another function, thereby pushing a new frame onto the stack. This frame will contain printf's local data. Once printf completes execution, its frame is popped and control returns to the main frame.

Recursive functions do the same. Every recursive call gets its own frame on the stack. Here's a horrible example of a recursive function which prints "hello" n times:

// hello_recursive.c

void hello(int n)
{
    if (n == 0) return;

    printf("hello\n");
    hello(n - 1);
}

int main()
{
    hello(2);
    return 0;
}

The above code gives the following output:

hello
hello

The function call stack will be something like this:

The first two calls will print out "hello" and make recursive calls with n - 1. Once we hit the last call with n = 0, we begin unwinding the stack.

Now imagine that we wish to print "hello" a million times. We'll need a million stack frames! I tried this out and my program ran out of memory and crashed. Thus, recursion requires O(n) space complexity, n being the number of recursive calls. This is bad news, since recursion is usually a natural, elegant solution for many algorithms and data structures. However, memory poses a physical limit on how tall (or deep, depending on how you look at it) your stack grows. Iterative algorithms are usually far more efficient, since they eliminate the overhead of multiple stack frames. But they can grow unwieldy and complex.

Tail Recursion

Now that we've understood what recursion is and what its limitations are, let's look at an interesting type of recursion: tail recursion.

Whenever the recursive call is the last statement in a function, we call it tail recursion. However, there's a catch: there cannot be any computation after the recursive call. Our hello_recursive.c example is tail recursive, since the recursive call is made at the very end i.e. tail of the function, with no computation performed after it.

    ...
    hello(n - 1);
}

Since this example is plain silly, let's take a look at something serious: Fibonacci numbers. Here's a non tail-recursive variant:

// Returns the nth Fibonacci number.
// 1 1 2 3 5 8 13 21 34 ...
int fib(int n)
{
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

You might argue that this is tail recursive, since the recursive calls appear at the end of the function. However, the results of the calls are added after they return. Thus, fib is not tail recursive.

Here's the tail-recursive variant:

int fib_tail(int n, int a, int b)
{
    if (n == 0)
        return a;   
    if (n == 1)
        return b;

    return fib_tail(n - 1, b, a + b);
}

The recursive call appears last and there are no computations following it. Cool.

You may be thinking, "Hmm, tail recursion is interesting, but what is the point of this?". Turns out, it is more than just a way of writing recursive functions. It opens up the possibility for some clever optimization.

Tail Call Optimization

Tail call optimization reduces the space complexity of recursion from O(n) to O(1). Our function would require constant memory for execution. It does so by eliminating the need for having a separate stack frame for every call.

If a function is tail recursive, it's either making a simple recursive call or returning the value from that call. No computation is performed on the returned value. Thus, there is no real need to preserve the stack frame for that call. We won't need any of the local data once the tail recursive call is made: we don't have any more statements or computations left. We can simply modify the state of the frame as per the call arguments and jump back to the first statement of the function. No need to push a new stack frame! We can do this over and over again with just one stack frame!

Let's look at our example with the non tail-recursive fib function. To find out the 3rd Fibonacci number, we'd do:

...
int third_fib = fib(3);
...

Assuming right-to-left precedence (i.e. the direction in which an expression is evaluated), the call stack would look something like this:

Quite large, isn't it? Imagine the size of the stack for finding out a later Fibonacci number! The problem here is that all the stack frames need to be preserved. You may use one of the local variables in the addition and hence the compiler needs to keep the frames around. If you look at the assembled output of this program, you'll see a call instruction for the fib function.

You can use the -S flag on GCC to output the assembly code. I've deliberately used the -O2 flag which uses the 2nd level of optimization among GCC's 0-3 levels. O2 enables tail call optimization. If you're not familiar with assembly, use GCC's -fverbose-asm flag while compiling. It adds your C code as comments before its corresponding assembled output. Here's the final command, which will produce a .s file:

gcc fib.c -S -O2 -fverbose-asm

This is what our tail call translates to:

# Snippet extracted from: fib.s

# fib.c:7:  return fib(n - 1) + fib(n - 2);
movl    %ecx, %edi  # ivtmp.22,
call    fib #
subl    $2, %ecx    #, ivtmp.22
addl    %eax, %edx  # _4, add_acc_7

Now, I'm not going to pretend that I understand this completely, because I don't. We only care about the instructions, none of the operand details. Notice the call fib instruction? That's the recursive call. It pushes a new frame onto the stack. Once that completes and pops, we have our addition instruction. Thus, we conclude that even at the 2nd level of optimization, the recursive calls cannot be eliminated, thanks to the addition.

    ...
    return fib_tail(n - 1, b, a + b);
}

Let's take a look at our tail recursive Fibonacci function, fib_tail. Once the above recursive call is made, there's no need to keep the local data around. There's no computation following the statement and it's simply returning the value returned by the recursive call; we could do that straight from the recursive call.

This presents an opportunity to simply replace the values of the local n, a and b variables with the ones used in the recursive call. Instead of a call instruction like before, the compiler can simply redirect the flow of execution to the first instruction in the function, effectively emulating a recursive call. But, without the overhead of one! Basically, the compiler goes:

This is how the call stack would look like:

You don't have to take my word for it, let's look at the assembler output for fib_tail. We compile the same way as before:

gcc fib_tail.c -S -O2 -fverbose-asm

For our tail recursive call, I see the following snippets of assembly:

# fib_tail.c:11:    return fib(n - 1, b, a + b);
    movl    %eax, %edx  # <retval>, b

# fib_tail.c:11:    return fib(n - 1, b, a + b);
    leal    (%rsi,%rdx), %eax   #, <retval>

# fib_tail.c:11:    return fib(n - 1, b, a + b);
    leal    (%rcx,%rdx), %esi   #, _5

# fib_tail.c:11:    return fib(n - 1, b, a + b);
    movl    %esi, %edx  # _5, b

As I said, I don't really understand assembly, but we're just checking if we've eliminated the call fib recursive calls. I'm not really sure how GCC is redirecting the control flow. What matters, however, is that there are no call fib instructions in the code. That means there are no recursive calls. The tail call has been eliminated. Feel free to dive into the assembly and verify for yourself.

Support

We've been using C in this post since GCC and Clang both support tail call optimization (TCO).
For C++, the case holds with Microsoft's Visual C++ also offering support.
Java and Python do not support TCO with the intention of preserving the stack trace for debugging. Some internal Java classes also rely on the number of stack frames. Python's BDFL, Guido van Rossum, has explicitly stated that no Python implementations should support TCO.
Kotlin even comes with a dedicated tailrec keyword which converts recursive functions to iterative ones, since the JVM (Kotlin compiles to JVM bytecode) doesn't support TCO.
TCO is part of ECMAScript 6 i.e. the JavaScript specification, however, only Safari's JavaScriptCore engine supports TCO. Chrome's V8 retracted support for TCO.
C# does not support TCO, however, the VM it runs within, Common Language Runtime (CLR) supports TCO.
Functional languages such as Haskell, F#, Scala and Elixir support TCO.

It appears that support for TCO is more of an ideological choice for language implementers, rather than a technical one. It does manipulate the stack in ways the programmer would not expect and hence makes debugging harder. Refer the documentation of the specific implementation of your favorite language to check if it supports tail call optimization.

Conclusion

I hope you understood the idea and techniques behind TCO. I guess the takeaway here is to prefer iterative solutions over recursive ones (that is almost always a good idea, performance-wise). If you absolutely need to use recursion, try to analyze how big your stack would grow with a non-tail call.

If both of these conditions don't work for you and your language implementation supports tail call optimization, go for it. Keep in mind that debugging will get harder so you might want to turn off TCO in development and only enable it for production builds which are thoroughly tested.

That's it for today, see you in the next post!

How Everest orchestrates pseudo tab-switching

Rohit Awate — Wed, 19 Sep 2018 18:04:07 +0000

Everest is a REST API testing client that I've been working on this year. Its written in JavaFX and aims to be a lighter, open-source alternative to Electron-based options like Postman. It occupied the #2 spot on GitHub's Java Trending for a week back in May this year when I released the first alpha. Today, I'll be talking about a memory optimization technique that I've implemented in the most recent alpha release.

I'm calling it pseudo tab-switching. Why? Because I'm an engineer and we like to give fancy names to simple stuff.

This article is quite technical and some stuff is done in a certain way because JavaFX demands so. However, the concept itself is framework/lanuguage-agnostic and you can use it with any other tech stack and make better use of your resources.

A disclaimer before we begin: I'm a student. I'm still attending university and have no professional experience. I have literally conjured up these ideas out of thin air and implemented them because they sounded promising. If you are an experienced developer, you may find this rather simple and obvious. Nonetheless, this was easily the most complex thing I've implemented in Everest and I'm excited to share it with you. Any feedback is welcome!

The Problem

This is the Dashboard in Everest. You can compose and send requests and also view their responses within it. You can have multiple of them open in separate tabs.

Prior to pseudo tab-switching (lets call it PTS, shall we?), for every new tab that you opened in Everest, a new Dashboard was created. That includes the view and the controller. Just a handful of tabs would push the memory usage north of 400MB.
This was really depressing and demotivating for me. At one point I even thought of removing the tabs altogether but that would mean giving in to a few electrons in my laptop and you won't be reading this article.

The Eureka moment

About two months back, as I was dreaming on a separate thread of my brain during a university lecture, I had an idea:

What if I load just one Dashboard and change the content within it every time the user switches to a different tab?

Makes sense right? All tabs show the same attributes (API endpoint, HTTP method, status code and so on) just with different values.

This would give the illusion of switching between tabs but you'd actually just be switching between states of the Dashboard. This would not only require way less memory but also facilitate better re-use of allocated memory. And that's where the name comes from!

Sounds simple, eh?

"Why did you have to write an article about this, Rohit? My cat could do this while asleep.", you'd say.

Well, you have one smart cat. Jokes aside, implementing this logic was not a smooth ride and I ran into some design issues that I had not anticipated but ended up with some solutions that I'm quite happy with and proud of.

The Challenges

So, barely able to contain my excitement, I bunked the remainder of the day's lectures, came home and fired up IntelliJ IDEA to implement my idea. (pun totally intended)

I wrote a new DashboardState class which would hold the values contained by all the UI elements ie the URL, the params, the HTTP method and so on. Everest already had a HomeWindowController class which handled the tabbing logic among other stuff. Before PTS, whenever a new tab was opened, HWC would simply create a new Dashboard and set it as the content for the new tab.

But since we've decided to use a single Dashboard and switch between its states, I wrote a new method in DashboardController called setState(DashboardState state). Now, every time a new tab is opened, I create a new, blank DashboardState object and set that as the state of the Dashboard using this method. HWC also holds a HashMap to keep track of which state belongs to which tab.

I also wrote a nifty little reset() method in DashboardController which clears the Dashboard of the previous tab's state.

By now, we can properly display a state in the Dashboard. But when you switch from tab A to tab B and return to A again, how do we display A again? This is something I realized quite late. Before making the switch from A to B, we need to store the state of A in the aforementioned map.

So I wrote another getState() method in DashboardController which returns the current state of the Dashboard, which can then be saved. Simply put, when the user shifts back to tab A, HWC finds its state from the map and then uses setState() to apply it to the Dashboard thereby completing the switch.

So far so good. But a big monster lurked by as Rohit rejoiced in his pseudo tab-switching glory..

The Monster

Before we get to the big problem, we need to understand how Everest handles HTTP requests. The requests obviously need to be made on a background thread. But Everest also needs to show a nice loading animation while the request is being made. To make this possible, I use JavaFX's excellent Service API. Not only does it allow me to make HTTP requests on a background thread, but also provides me with methods to update the UI concurrently. These include setOnRunning(), setOnSucceeded() and setOnFailed() which accept lambdas that update the UI.

Everest uses setOnRunning() to trigger the loading animation of the Dashboard, setOnSucceeded() to display the response (status code, body, elapsed time and so on) and setOnFailed(), the error messages. What I intend to establish here is that these lambdas act on the Dashboard.

But, if the user initiates a request in tab A and switches to tab B while the request is still running on the Dashboard, setOnSucceeded() would display tab A's result when tab B is selected.

The lambdas, somehow, need to be removed on a tab switch. But, we also need to keep the request running because if it is terminated or even halted, the utility of multi-tabbing ceases to exist.

Here's an elegant solution that I came up with, which I'm quite proud of.

Beating the Monster

Remember that getState() method from DashboardController? I added a simple check within that to see what the Dashboard is currently doing. If a request is running, it will take that Service object, and hand it over to the DashboardState.

Now comes the clever bit: DS decommissions the lambdas that modified the Dashboard and adds its own which modify its own members!

For example, if DashboardController's lambda forsetOnSucceeded()displayed the status code of the response by modifying the text value of a Label onscreen, the corresponding one set by DashboardState would modify the statusCode attribute within itself.

Now, when the user switches back to tab A, A's state will be applied to the Dashboard which in turn will have been updated by the lambdas set by DashboardState!

TLDR? PTS allows you to switch between tabs even when you've got requests running in one or more of them.

The Gains 💪

This comparison was made between Alpha 1.2 (without PTS) and the upcoming Alpha 1.4 (with PTS) with 7 tabs in each instance. With more tabs, the difference can become even larger since v1.4 has to only create another instance of a DashboardState rather than a full Dashboard like v1.2 does.

There is still scope for tiny improvements here and there, which will be done once we hit a feature-lock, which should happen by the end of this year or early next year.

Summing it up

It all boils down to this simple algorithm:

Save the state of the Dashboard
Reset the Dashboard
If a new tab is being opened, create and then apply a blank new DashboardState to the Dashboard
If switching back to an existing tab, fetch its state from the map and apply it to the dashboard

Here's a formal-ish definition for pseudo tab-switching:

If you have multiple UI elements that house a common UI element, then instead of creating multiple instances of the latter, create just one and share it between multiple instances of the former by switching between states.

"Okay, now shut up Rohit!"

Yes, I hear you! This has been a very long post with a galaxy worth of jargon. I was going to make some announcements and ask a couple of questions but lets save it for next time.

Check out Everest on GitHub and try out Alpha 1.3. Let your developer friends know about it. Stay tuned for future updates as we're approaching a stable release early next year.

RohitAwate / Everest

A beautiful, cross-platform REST client.

Everest (formerly RESTaurant) is an upcoming REST API testing client written in JavaFX.

Everest running on Windows 10.

Why Everest?

Everest is written in Java. Thus, it is significantly lighter on resources and more responsive than its Electron-based alternatives like Postman. It aims to provide the same level of functionality in a lighter, native but equally slick package.
Aesthetic is very important. With a gorgeous, flat design, Everest is a pleasure to look at and to work with. It is also entirely theme-able.

I want you to want to use it!
Being a Java application, Everest is inherently cross-platform. It will run anywhere there's a JVM.
Everest will offer cloud synchronization of your projects powered by Summit. It will be available as a cloud service early next year or you may also choose to self-host it.

Live Features 🔥

All of the most common

…

View on GitHub

I hope you found something of value here. PTS can be useful even if you're doing front-end web development or native mobile app development.

Thank you for reading this! Leave a comment if you have suggestions, questions or anything else to say.

You may now Alt + Tab back to your text editor.
Goodbye! :)

Everest: A gorgeous REST API client written in JavaFX

Rohit Awate — Wed, 02 May 2018 15:31:23 +0000

Hi! I'm Rohit, a student currently in the second-year of Computer Engineering. For the past 4 months, I've been building a REST API client with JavaFX. I'm really excited to share my work with you folks!

My goal with this project was to make something similar to Postman and Insomnia but in a lighter package using JavaFX without compromising on the beautiful design that Electron-based applications come with, while maintaining a comparable level of functionality. I'm currently focused on optimizing every thing that comes under my radar but I also add new features occasionally.

Here are some of the core features:

A gorgeous user-interface.
Making GET, POST, PUT, DELETE and PATCH requests. (duh)
Multi-tab layout.
History tab to quickly search through your recent requests.
Support for custom themes via JavaFX CSS!
A Visualizer which shows you a nice tree for your response bodies
Being written in Java, Everest is inherently cross-platform.

Okay enough, my beautiful README is getting jealous so why don't you go check her out on GitHub: https://github.com/RohitAwate/Everest

Please try out the alpha and let me know what you think! :)