How to improve the memory usage in nodejs code?

Question

I tried one code at hackerearth : https://www.hackerearth.com/practice/data-structures/stacks/basics-of-stacks/practice-problems/algorithm/fight-for-laddus/description/

The speed seems fine however the memory usage exceed the 256mb limit by nearly 2.8 times. In java and python the memory is 5 times less however the time is nearly twice.

What factor can be used to optimise the memory usage in nodejs code implementation?

Here is nodejs implementation:

// Sample code to perform I/O:

process.stdin.resume();
process.stdin.setEncoding("utf-8");
var stdin_input = "";

process.stdin.on("data", function (input) {
    stdin_input += input;                               // Reading input from STDIN
});

process.stdin.on("end", function () {
    main(stdin_input);
});

function main(input) {

    let arr = input.split("\n");
    let testCases = parseInt(arr[0], 10);
    arr.splice(0,1);
    finalStr = "";
    while(testCases > 0){
        let inputArray = (arr[arr.length - testCases*2 + 1]).split(" ");
        let inputArrayLength = inputArray.length;
        testCases = testCases - 1;
        frequencyObject = { };
        for(let i = 0; i < inputArrayLength; ++i) {
            if(!frequencyObject[inputArray[i]])
            {
                frequencyObject[inputArray[i]] = 0;
            }
            ++frequencyObject[inputArray[i]];
        }

        let finalArray = [];
        finalArray[inputArrayLength-1] = -1;
        let stack = [];
        stack.push(inputArrayLength-1);
        for(let i = inputArrayLength-2;  i>=0; i--)
        {
            let stackLength = stack.length;
            while(stackLength > 0  &&  frequencyObject[inputArray[stack[stackLength-1]]] <= frequencyObject[inputArray[i]])
            {
                stack.pop();
                stackLength--;
            }
            if (stackLength > 0) {
                finalArray[i] = inputArray[stack[stackLength-1]];
            }  else {
                finalArray[i] = -1;
            }
            stack.push(i);
        }
        console.log(finalArray.join(" ") + "\n")
    }

}

jfriend00 · Accepted Answer · 2019-11-26 05:57:56Z

What factor can be used to optimize the memory usage in nodejs code implementation?

Here are some things to consider:

Don't buffer any more input data than you need to before you process it or output it.
Try to avoid making copies of data. Use the data in place if possible. Remember that all string operations create a new string that is likely a copy of the original data. And, many array operations like .map(), .filter(), etc... create new copies of the original array.
Keep in mind that garbage collection is delayed and is typically done during idle time. So, for example, modifying strings in a loop may create a lot of temporary objects that all must exist at once, even though most or all of them will be garbage collected when the loop is done. This creates a poor peak memory usage.

Buffering

The first thing I notice is that you read the entire input file into memory before you process any of it. Right away for large input files, you're going to use a lot of memory. Instead, what you want to do is read enough of a chunk to get the next testCase and then process it.

FYI, this incremental reading/processing will make the code significantly more complicated to write (I've written an implementation myself) because you have to handle partially read lines, but it will hold down memory use a bunch and that's what you asked for.

Copies of Data

After reading the entire input file into memory, you immediately make a copy of it all with this:

let arr = input.split("\n");

So, now you've more than doubled the amount of memory the input data is taking up. Instead of just one string for all the input, you now still have all of that in memory, but you've now broken it up into hundreds of other strings (each with a little overhead of its own for a new string and of course a copy of each line).

Modifying Strings in a Loop

When you're creating your final result which you call finalStr, you're doing this over and over again:

finalStr = finalStr + finalArray.join(" ") + "\n"

This is going to create tons and tons of incremental strings that will likely end up all in memory at once because garbage collection probably won't run until the loop is over. As an example, if you had 100 lines of output that were each 100 characters long so the total output (not count line termination characters) was 100 x 100 = 10,000 characters, then constructing this in a loop like you are would create temporary strings of 100, 200, 300, 400, ... 10,000 which would consume 5000 (avg length) * 100 (number of temporary strings) = 500,000 characters. That's 50x the total output size consumed in temporary string objects.

So, not only does this create tons of incremental strings each one larger than the previous one (since you're adding onto it), it also creates your entire output in memory before writing any of it out to stdout.

Instead, you can incremental output each line to stdout as you construct each line. This will put the worst case memory usage at probably about 2x the output size whereas you're at 50x or worse.

Collectives™ on Stack Overflow

How to improve the memory usage in nodejs code?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related