DEV Community: Alex Woods

Kotlin Algorithm Challenge No. 3

Alex Woods — Wed, 22 Jan 2020 18:13:40 +0000

Originally posted here

The following problem is the Reverse Integer problem on LeetCode.

Problem

Given a 32-bit signed integer, reverse its digits.

fun reverse(x: Int): Int {
    // TODO
}

Solution

This problem is not too difficult (i.e. this is absolutely a fair interview question!). The approach we're going to take is breaking down the number by multiples of 10, and using the broken off piece to construct the reversed number.

There might be a temptation to convert the value to a string, reverse it, then convert it back again. Don’t do that, it's completely against the spirit of the problem. I also trust math more than I trust type conversion, if code like this were to ever make it into production.

fun reverse(x: Int): Int {
    var int = x
    var sum = 0

    while (int != 0) {
        val digit = (int % 10)

        val newSum = 10*sum.toLong() + digit.toLong()
        check(newSum > Integer.MIN_VALUE && newSum < Integer.MAX_VALUE) {
            "Integer overflowed, input too large"
        }

        sum = newSum.toInt()
        int /= 10
    }

    return sum
}

You can see the progression of our sum variable in the following example.

1234

10*0 + 4 = 4
10*4 + 3 = 43
10*43 + 2 = 432
10*432 + 1 = 4321

Writing Good Kotlin Code

But how does idiomatic Kotlin code fit into this problem?

Pure Functions

A pure function is a function that doesn't mutate it's input, and it has no side effects. Because of these two things, when a pure function is run multiple times with the same input, it gives the same result.

It's not obvious in the above code, but Kotlin is making me go out of my way to write a pure function. Try the following:

fun foo(x: Int) {
    x = 4  // an error pops up: "Val cannot be reassigned"
}

In a similar vein, collections are immutable by default.

fun foo(list: List<Int>) {
    list.add(4) // nope! the compiler won't allow it!
}

The above isn't allowed, because the List interface extends the Collection interface, which doesn't contain an add method. If you want an add method, you have to declare MutableList, which extends MutableCollection. And putting MutableList as a type of a function input parameter should set off a red flag in your head.

Check

The check function checks some condition. If it is false, it throws an IllegalStateException. We can use it to make sure people are only calling our function at the right time.

Similar to check is the function require. We pass it a condition, and if false, it throws an IllegalArgumentException. So it is used for validating input. e.g.

fun poundsToKilograms(weightInPounds: Double) {
    require(weightInPounds >= 0) {
        "There's no such thing as a negative weight."
    }

    return weightInPounds / 2.2
}

Augmented Assignment Operators

The slightly funny looking operator /= means divide and then assign. That line is equivalent to the following.

int = int / 10

Summary

Thank you for reading the most recent Kotlin Algorithm Challenge! If you want to learn more about Kotlin, you can see all the articles I’ve written about it here.

How the Node.js Event Loop Polls

Alex Woods — Thu, 22 Aug 2019 00:34:33 +0000

Say we are a Node.js client, and we've made a request to some server. What happens as we're waiting for that response? How does the event loop know when to put the associated callback on the event queue?

Say we are a Node.js client, and we've made a request to some server.

What happens as we're waiting for that response?
How does the event loop know when to put the associated callback on the event queue?

Demultiplexing and the event loop

Node.js's event loop is implemented in a library called libuv, which is also used by Julia and Python. We're going to dive into its internals.

The following is 1 iteration of the event loop:

uv__update_time(loop);
uv__run_timers(loop);
uv__run_pending(loop);
uv__run_idle(loop)
uv__run_prepare(loop);

// our method of interest
+------------------------------+
| uv__io_poll(loop, timeout);  |
+------------------------------+

uv__run_check(loop);
uv__run_closing_handles(loop);

The method we care about, uv__io_poll, basically does the following:

Say the event loop is watching n open sockets 👀, because we have n unresolved requests. It does this by maintaining a watcher queue, which is just a list of n watchers—basically a socket with some metadata.

Then, the polling mechanism recieves an event. At notification time, it doesn't yet know which open socket this corresponds to.

All of our watchers (in the watcher queue) are identified by a file descriptor. This is just an integer that acts as an ID for an open I/O resource. This is a common thing in an operating system.

The event we received contains an id field (named ident), which is a file descriptor. Once we have the file descriptor, we can get the watcher. This is the step that gives this process the name demultiplexing.

Finally, once we have the watcher, we can get the callback to put on the event queue.

The polling mechanism?

In the above description, we glossed over something that seems kind of magical—what is the polling mechanism and how does event loop receive an event?

The short answer is that it uses a system call to be notified of such events. Which one depends on the operating system.

OS	Function
FreeBSD (Mac)	kqueue
Linux	epoll
Windows	IOCP

Let's take a look at kqueue, but first let's review what happens when we our computer receives a packet.

When the kernel gets a packet from the network interface, it decodes the packet and figures out what TCP connection the packet is associated with based on the source IP, source port, destination IP, and destination port. This information is used to look up the struct sock in memory associated with that connection. Assuming the packet is in sequence, the data payload is then copied into the socket’s receive buffer. [3]

How kqueue recieves a notification:

                           +--------------------------+
                           |                          |          +-------------+         +-------------+   
                           |                          |          |             |         |             |   
receives packet +--------->+    Network Interface     +--------->+   Socket    +-------->+   kqueue    |   
                           |                          |          |             |         |             |   
                           |                          |          +-------------+         +-------------+   
                           +--------------------------+

After this occurs, the socket (our event-generating entity of interest) traverses the kqueue's list of registered events (called knotes), and finds the one it belongs to. A filter function decides whether it merits reporting. [2] kqueue would then report it to the user program.

Here are some of the events an application might register with kqueue.

Event name	Operation tracked
EVFILT_READ	Descriptor has data to read
EVFILT_AIO	Asynchronous I/O associated with descriptor has completed
EVFILT_TIMER	An event-based timer has expired

kqueue is actually pretty simple. It's just a FreeBSD system call which provides notification to a user program of a kernel event.

In our case, libuv is the user program.

Conclusion

This has certainly helped me understand the core of what libuv is. It provides Node with its event loop; it uses callback style API's, and most importantly, it abstracts away the complexity of interfacing with system calls.

It's "polling" mechanism is not inherently that complex, because the system calls it uses are event-driven. It just has to keep a data structure of the callbacks registered for each event.

Sources

How similar is the execution of Java and JavaScript?

Alex Woods — Sun, 14 Apr 2019 00:00:00 +0000

In this article, I will compare the execution of Java and JavaScript. I am intentionally avoiding a lot of details about memory, as that is a whole other topic.

Execution at the processor level

With each passing clock cycle, the processor executes a single microinstruction. These are strings whose bits drive the control lines of the CPU. We get a series of microinstructions by the translation of an instruction (frequently called machine code). The set of all available instructions for a processor is called the Instruction Set Architecture (ISA), which in a sense is the API of your computer’s processor.

source code -> instructions (now within processor) -> microinstructions (executed each clock cycle)

Statements in a program can be taken by a compiler and turned into machine code (instructions). The best example of this is C. Different processors, however, provide different Instruction Set Architectures. Does this mean we have to write a different compiler for each processor? (Yes, it does.) This is a problem as compiler’s do more and more work for the programmer.

We can solve this by keeping all the added features in our program executor the same, except for the processor. If we virtualize the processor, and provide an ISA specially designed for the execution of the language in question, we now have a component we can take in and out, as we move from one OS to another (presumably with different processors).

Virtualizing the processor

As alluded to above, both the languages in question (Java and JavaScript), provide an abstraction on top of machine code in order manage this complexity. This “abstraction of machine code” is called bytecode. In Java, it is the .class files, and with JavaScript it varies depending on the engine in question. To see the bytecode used by the V8 engine (the one used in Node.js and Chrome), execute it with the --print-bytecode flag.

To run a JavaScript program purely with V8
(excluding Node’s runtime), install V8 and run
v8 hello.js (where hello.js is your program)
e.g. v8 --print-bytecode hello.js
(Because seeing the bytecode of Node’s runtime isn’t the best for education purposes).

When I say “virtualizing the processor”, what I mean is that we are executing the program in a virtual machine. We have some entity (either the JVM interpreter or the Ignition bytecode executor), that knows how to execute their version of bytecode. What we are using here is called a process virtual machine. This is in stark contrast to a system virtual machine, which has its own guest operating system (think VMWare). A process virtual machine is much lighter, and its sole purpose is executing a program. To be clear, it does further virtualize other things, such as memory, which means there exists a mapping. For simplicity, the mapping is just a direct mapping. Note that memory is already virtualized on the host OS; the memory blocks given to a process appear continuous, but are not guaranteed to be so. The most complicated thing we are abstracting away is the processor and it’s machine code.

In the JVM, for example, the interpreter takes a line of bytecode, and knows how to execute it without providing further translation into machine code.

In V8, the Ignition interpreter acts in a similar way. it takes a statement from the parsed AST, turns it into bytecode, and executes it by itself.

Let’s dive deeper into the details of the two.

How the JVM Executes Programs

Let’s say we have some Java source code. We use the Java compiler (javac) to turn it into bytecode (.class files). Then we feed it into the JVM.

The JVM takes it, and after some initialization steps (class loading, bytecode verifying, etc.), a statement of bytecode arrives at the interpreter, which executes it.

As execution continues, if some piece of code (e.g. a function) has been executed a certain number of times (i.e. it is “hot”), the JVM execution engine contains a JIT optimizing compiler which will turn it into machine code, allowing it to execute faster.

Note that the “JIT compiler” in this case goes from bytecode to machine code.
JavaScript’s JIT compiling, in contrast, goes from source code to bytecode.

How the V8 Engine Executes Programs

In contrast, JavaScript is JIT compiled. That means there is no pre-compilation step before it is fed into the execution engine; we feed the engine raw source code.

Say, we have some JavaScript source code. It is parsed and turned into an AST. That is then fed into Ignition, V8’s interpreter. Ignition turns that into bytecode, and executes it.

Just like before, if we discover a hot function, we have an optimizing compiler to turn that into machine code. In V8, this entity is called TurboFan.

Going to steal Franziska Hinkelmann’s picture, from her great blog post on the topic.

Note – Above I talked about process virtual machines. V8 is pretty sparse on those kind of internal details, but I did read enough to convince myself that they use a process virtual machine. (See here, here, and here).

Similarities Between Java and JavaScript Execution

Both are run inside process virtual machines. They both have their own “bytecode”, which is just an abstraction of machine code. Those process virtual machines execute their corresponding bytecode.
They both take the same approach for code that is “hot”. That is, an optimizing compiler turns the bytecode into machine code, using profiling information accumulated throughout execution.

Differences Between Java and JavaScript Execution

There is one major difference here—JavaScript is JIT compiled, Java is not. Due to this, there’s no abstraction in between the JavaScript language and it’s execution engine (V8, in this case). That means it’s impossible to use V8 to execute another language.

The JVM, on the other hand, only knows about .class file bytecode. This gives space for other language that can compile to .class files. Enter Scala, Groovy, Clojure, and Kotlin.

It’s ironic because this layer of abstraction only exists because there was a necessity to send bytecode over the network, around the time Java came out (early World Wide Web days, when Java was supported in the browser). Nowadays, this doesn’t matter at all. These days we send JavaScript source code over the network, and the browser uses an execution engine (like V8) to execute it.

I find this point fascinating, and I believe this indirection might lead to the JVM sticking around for a very long time, because we can choose to use it even if we don’t want to use Java. It’s appealing for language designers, because over half the work is done for them—all they have to do is design a language spec and a compiler to .class bytecode.

Conclusion

After researching and writing this, my opinion is now that the way that JVM languages and JavaScript are executed is much closer than I originally imagined. Hope ya learned something.

Originally posted here.