So I Added New Linting Rules

An issue was filed for Telescope to address consistency and proper use of async/await + promises and fix them. I added new linting rules. Ran an npm test:

Oh my god.

Amazon Algorithm Solution

I was going over a blog by a classmate of mine who's been contributing a lot to our internal project. I stumbled upon a post of his regarding Amazon's online technical interview question and decided to take a crack at it in Javascript.

It is pretty simple: Given 2 lists of numbers and a maximum, find the maximum sum of a number from list2 that is smaller or equal to the given maximum as well as the number of occurrences.

This is the first attempt of what I had, with what I understood as the requirements

// Given 2 lists of numbers and a maximum, find the maximum of sum of a number from 
// list1 + a number from list2 that is smaller or equal to the given maximum, as 
// well as the number of occurrences.

function find(list1, list2, max){
    let resultsArr = [];
    // we will filter list2 for nums that are small or equal to given max
    list2.filter((x) => {
        return x <= max
    })
    // we will then use the filtered list and get a sum of each
    .map((filteredNum) => {
        list1.forEach((num) => {
            resultsArr.push(num + filteredNum);
        })
    })

    console.log(resultsArr.length)
    console.log(Math.max(...resultsArr))
}

let list1 = [5,10,15]
let list2 = [1,2,3]
find(list1, list2, 2);

It works and does as expected, but upon re-reading the requirements again. I decided to do another one. This is the second attempt of what I had, with revised understanding of requirements

// Given 2 lists of numbers and a maximum, find the maximum of sum of a number from 
// list1 + a number from list2 that is smaller or equal to the given maximum, as 
// well as the number of occurrences.

function find(list1, list2, max){
    const results = []
    list1.map((num1) => {
        list2.forEach((num2) => {
            const num = num1 + num2;
            if (num <= max){
                results.push(num);
            }
        })
    })

    const maxResult = Math.max(...results);
    const finalResult = results.filter((num) => {
        return num == maxResult;
    })

    console.log('The list of sums: ' + results);
    console.log('The largest sum less than or equal to ' + max + ' is ' + maxResult);
    console.log('The # of occurrences for the largest sum is ' + finalResult.length);
}

let list1 = [13,13,15]
let list2 = [1,2,3]
find(list1, list2, 15);

Tested it and it works!

The list of sums: 14,15,14,15
The largest sum less than or equal to 15 is 15
The # of occurrences for the largest sum is 2

Further tweaks I could do, would be to have a variable to hold the max value for the current iteration and have a counter that will track, instead of pushing to an array and then doing all the work at the end

SPO600 Project Post 5

After reviewing other's people work on their projects. I've realized I forgot to test on the other systems Bbetty and Xerxes. I first attempted to install Redis onto Xerxes, our x86_64 system... No go, apparently everyone loves testing on the machine so much there's no more storage space left to install my project.

So that left Bbetty, wow. This machine is much faster than Aarchie, its sibling Aarch64. The same benchmarks I was running on Aarchie were completed in half the time:

Average run time was about: 25.67 seconds

As my optimizations didn't work on Aarchie, I was pretty sure they weren't going to work on Bbetty either, but for the sake of curiosity I decided to test them and here are the results:

Average run time was about: 25.64 seconds, 0.02 faster, but again like Aarchie, this was a small sample out of many I did and they weren't always reliably faster.

I doubled the amount of SET operations to 2 million to see if there were any efficiencies gained, because perhaps there might be some if there was more requests processed? I got average run times of about 51.435 seconds. A big giveaway whether optimizations gained from my code changes would be to check the throughput of the requests per second completed. They remained relatively the same if not a bit lower sometimes than the non modified code. So I'm pretty sure I can conclude my changes have failed to produce any optimizations. 

For anyone extremely curious about the call graph for the benchmark of the 1 million SET operations (I apologize for the poor picture quality):

SPO600 Course Wrap Up

We're at the end of the course! This felt like a really long course, but very interesting and fun. Throughout all of my years at Seneca I never really got to interact close to the hardware level, and this course finally allowed me to. I can finally say I've programmed in assembly language!

Overall, I found this course extremely difficult, I'd listen to the lecture in class, look at the lab briefly and kind of just close the window. The labs themselves were pretty challenging and required us to look up a lot of stuff as well as reading other people's blogs if we were stuck to get an idea of how to proceed. Which isn't that much different from the real world when we do get stuck. I recall setting aside a whole weekend just to do the weekly labs.

As a student who only learned the basics of C for a semester as an introductory course, trying to understand the C code being used or talked about in class was also challenging. That coupled with the fact that our project selections were recommended to be in the C language also made it extremely hard, as I'm assuming most of the libraries are written by people who are very fluent in C. Trying to read the code is kind of like deciphering a language we barely know.

All this isn't to say I didn't enjoy the course, it was quite the opposite. I don't think I've found another course aside from this(SPO600) or OSD600 where I decided to spend so much time on it. Our professor, Chris Tyler was amazing, with lots of professional experience and also keeps himself up to date with the industry. During the project phase of the course he'd show us possible optimizations for libraries every week as he knew quite a bit of us were frustrated on trying to find one. He also tried help remove any roadblocks we encountered by tackling them in class.

I'm a little disappointed and sad I wasn't able to find an optimization for my project Redis, as I thought it would've been pretty cool to put it on the resume for potential employers and also the fact that we're using Redis as part of an internal project for the school. It was fun though doing instrumentation and profiling on Redis and analyzing the results to see if my changes improved the run time of SET operations.

Lastly, I'd like to thank Professor Tyler for teaching this course and also spending time on analyzing the results of the profiling and instrumentation of my project!

SPO600 Project Post 4

So this is the post where I'm testing my supposed optimizations. A quick recap, I made changes to Redis's version of the reallocate function. It will now only reallocate memory if the size of the new pointer is larger than the current size pointer, otherwise it will just 0 the block of memory.

These are the results of running the following command
-redis-benchmark -t set -n 1000000

which means we're running 1 million set commands with 50 parallel clients of 3 bytes payload.

These are the results without any optimizations



Average run time is about 79.3775 seconds

Here are the results after some preliminary modifications:

Average run time is about 81.8175 seconds. Wait... that isn't an optimization. It has become slower! After some slight checking of the "optimizations" I made, I realized I missed updating an area. Here are the new results after:

These are the more notable results. As I was testing it randomly throughout the day, I got some results that were 0.14s-0.2s faster to times that were sometimes up to 1.5s -2 s slower. As explained in class by Professor Tyler, I don't think the upstream will accept this code change, as it is not reliably faster AND also potential improvements are only roughly 2.5% gains.

SPO600 Project Post 3

Continuing from the second post, I found the file calling all the je_malloc related functions... in a file called zmalloc.c.

One of the key things we could look at was the following:

• check if Redis was trying to allocate new memory for set operation
• if it did, could we just overwrite the already allocated memory block for another set operation?

 I was able to find the reallocate function with the code below:

Upon going through the code you'd notice in the second #ifdef HAVE_MALLOC_SIZE scenario, 

  oldsize = zmalloc_size(ptr);
  newptr = realloc(ptr,size);
  if (!newptr) zmalloc_oom_handler(size);

  update_zmalloc_stat_free(oldsize);
  update_zmalloc_stat_alloc(zmalloc_size(newptr));
  return newptr;

The code doesn't check if the new size being defined is smaller or equal than the already allocated space. What we could potentially do is what Professor Tyler suggested last week, here we can zero the memory instead of reallocating for sizes that are smaller than the current size(oldsize).

Thankfully the C library has a function in the following signature 

void memset( void *str, int c, size_t n)

str - the pointer to the block of memory

c - the value to bet set

n - number of bytes set to the value

With that, we can change the code to look like:

    oldsize = zmalloc_size(ptr);
    if (oldsize >= size){
        memset(ptr, 0, oldsize);
        return ptr;
    }
    else{
        newptr = realloc(ptr,size);
        if (!newptr) zmalloc_oom_handler(size);
        update_zmalloc_stat_free(oldsize);
        update_zmalloc_stat_alloc(zmalloc_size(newptr));
    }
    return newptr;

On a side note, at the end of the lecture class, Professor Tyler informed us of an ARM instruction that zeros the data cache by address and X86_64 should have a somewhat equivalent I can implement as a possible optimization. Later when we met again, he explained to me the ARM instruction cannot be done as the Exception Level has to be at least 1 or higher in order not to trap.

In a search for the other optimizations we could do for Redis, he suggested running a strace with the process ID of the redis-server. So I would run Redis server using redis-server, add a strace to the process and then running the redis-benchmark to check for system calls. With the file obtained from the strace, I'd look for systems calls of brk or sbrk where the program is allocating more memory. Unfortunately, this didn't result in anything.

As soon as I can get gprof working on redis-server, I will try to find whatever is calling the je_malloc_usable_size ~8.5% of the time for the execution of the Redis server. As the professor has noted, the program spends close to 16.5% if its execution time calling je_malloc_usable_size, je_free and je_malloc.

Release 0.4 Third Week and Course Wrap Up

I'm pretty sure this is the third week of Release 0.4. I finally got to tackle an issue regarding Redis! Truthfully, I wished I did more Redis related work as it seems interesting. My issue can be found here.

I didn't do much work, most of the heavy lifting was done by people who worked on the storage.js portion of the code and the people who worked on creating the post object and mapping the appropriate fields. The week before this, we had an issue with the queue and were not able to figure out what to write in order to output things when a worker was done processing a job.

I'm imagining after lots of frustration on the professor's part, he managed to figure out what the appropriate code was:

feedQueue.on('completed', callback)

From there it was all about writing a callback that dealt with the job and results

  feedQueue.on('completed', async (job, results) => {

    try {

      await Promise.all(results.map(result => storage.addPost(result)));

    } catch (err) {

      logger.error({ err }, 'Error inserting posts into database');

    }

A simple explanation of the code:

On completion of the worker processing the job from the queue, it will store each individual post object into the Redis server with a unique ID. Once all the posts from the job are added, a promise will be returned, if there is an error during this this, an error will be displayed.

When it came to using functional programming, I never really got to practice them. I learned about .map, .reduce and .filter in java, but we only used it once for a lab and most of the time I have still been using for loops. It was nice to be reminded of how to use them again.

Lastly, when working on my first PR for this project which was the feedParser, I've read about Promise.all, Promise.resolve, Promise.reject and the other variations while learning about async/await. I didn't really understand it, but I'm now grateful this came up on my issue as the professor was able to explain how to use it. 

For anyone, who's wondering about Promise.all(), it is used handle a bunch of Promises. In this scenario on the line starting with await, each posts being stored to Redis is an asynchronous task and may take longer or shorter than others, we're going to wait until all the posts are stored from the job before returning a promise.

Very last note, this blog marks the end of the OSD600 course. I have to say, this course exceeded any expectations I had. It was very highly recommended by the professor from my Data Structures and Algorithm course, Catherine Leung as she mentioned there was no other course like it and the experience you get from the course is whatever you put in. I can only repeat the words she said word verbatim. For others, if you happen upon this blog and are wondering whether you should take OSD600, do it! I've previously read reviews that students should already be involved in open source or they'll have a bad time, I came in with 0 knowledge and it was extremely fun and a great learning experience. I'd also like to thank the professor for teaching this course, his patience and for reviewing close to 350-400 pull requests from his class of 60 students. That must have been hell.

Release 0.4 Second Week

First failed PR!

Second week into Release 0.4 I was decided to take on the task of trying to implement danger js.

First, let us talk about the situation, a lot of contributors in the class were having issues with their package and package-lock files. The usual process would usually be like this

1. update master to current upstream with git pull upstream master
2. enter npm install to install all dependencies for libraries being used

Seems like this was a problem for a lot of people, whenever they pulled, they usually forget to update their package-lock with npm install. Afterwards, when contributors try to submit their PRs, our CIs' (Travis + Circle) complain something is off with the contributor's package-lock.

To combat this, the professor suggested we trying implementing a library called danger js. It is a library that allows users to set warnings that can also be used by the CI services to inform users making a pull request about the status of their files. We were interested in two use cases:

• reminding users if their package.json file has changed but their package-lock.json file has not
• reminding users if any of the src files have been changed, but tests for the changed src files have not been modified

The first one would always remind users to do an npm install so their package-lock.json is synchronized with the one on master assuming they did not install new libraries to the project

The second one would always remind users, if any of the source files have been changed, maybe they should update or write new tests to accommodate the changed code.

The process is pretty easy, users create a file called dangerfile.js and write what conditions they want to check to trigger messages to be displayed. An example is displayed below.

const apps = includes(danger.git.fileMatchc, '../*.js');

const tests = includes(danger.git.fileMatch, '../../test/*.test.js');

if (apps.modified && !tests.modified) {
  const message = `Changes were made to file in src, but not to the test file folder`;
  const idea = `Perhaps check if tests for the src file needs to be changed?`;
  warn(`${message} - <i>${idea}</i>`);
}

After preparing a danger file, the next step is to integrate it with a CI service, the website for the library has specific instructions depending on the CI service... this is where things get kind of dicey and where the professor decided against implementing this library.

To be able to integrate with Github, users have to generate their own Github API token and add it to their CI service, that isn't too bad. What is bad though is in order for danger js to work with the CI, users also have to enable an option displaying the API token in the build log, this is dangerous as the Github API token is private for every account, publicly displaying this token is pretty bad as that token uniquely identifies an account.

In popular practice this isn't so bad, because a bot is usually used to implement danger js and publicly displaying the bot's token wouldn't have too much of a negative effect (it is a bot). But the thought of having to set up and maintain a bot was too much work, and the alternative to not using a bot would require every user to set their own token in the CI services. With all these requirements needed to get the danger js service working, the professor decided we should not move ahead with this idea.