HolyJS 2019: Debriefing from SEMrush (Part 2)



    This is the second part of the analysis of tasks from our booth at the HolyJS conference , held in St. Petersburg on May 24-25. For a larger context, it is recommended that you first read the first part of this material. And if Countdown Expression has already been completed, then welcome to the next step.

    Unlike obscurantism in the first task, the next two already have some hint of the applicability of normal applications in life. JavaScript is still developing quite fast and solutions to the problems suggested highlight some of the new features of the language.

    Task 2 ~ Done by Ones


    It was assumed that the code would execute and print answers to the console in response to three requests, and then “done”. But something went wrong ... Correct the situation.

    ;(function() {
      let iter = {
        [Symbol.iterator]: function* iterf() {
          let fs = ['/1', '/2', '/3'];
          for (const req in fs) {
            yield fetch(req);
          }
        }
      };
      for (const res of iter) {
        console.log(res);
      }
      console.log('done');
    })();
    

    Research problem


    What do we have here? This is an iterable iter object that has a well-known Symbol.iterator symbol defined through a generator function . An array fs is declared in the body of the function , the elements of which fall into the fetch function in turn to send a request and the result of each function call is returned through yield . What requests does the fetch function send ? All elements of the array fs - is a relative path ( path ) to the resources with the numbers 1, 2 and 3 respectively. So the full URL will be obtained by concatenating location.origin with the next number, for example:

    GET https://www.example.com/1

    Next, we want to iterate the iter object through for-of , in order to execute each request in turn with the output of the result, after all - print “done”. But that doesn't work! The problem is that fetch is an asynchronous thing and returns a promise, not a response. Therefore, in the console we will see something like this: Actually, the task comes down to resolving these same promises.

    Promise {pending}
    Promise {pending}
    Promise {pending}
    done



    We have async / await


    The first thought may be to play with Promise.all : give it our iterable object, then the output to the console is “done”. But he will not provide us with sequential execution of requests (as required by the condition), but simply send them all and wait for the last answer before the general resolution.

    The simplest solution here would be await in the for-of body to wait for the resolution of the next promise before output to the console:

    for (const res of iter) {
      console.log(await res);
    }
    

    For await to work and "done" to be displayed at the end, you need to make the main function asynchronous via async :

    ;(async function() {
      let iter = { /* ... */ };
      for (const res of iter) {
        console.log(await res);
      }
      console.log('done');
    })();
    

    In this case, the problem has already been solved (almost):

    GET 1st
    Response 1st
    GET 2nd
    Response 2nd
    GET 3rd
    Response 3rd
    done

    Asynchronous Iterator and Generator


    We will leave the main function asynchronous, but for await there is a more elegant place in this task than in the for-of body : this is the use of asynchronous iteration through for-await-of , namely:

    for await (const res of iter) {
      console.log(res);
    }
    

    Everything will work! But if you turn to the description of this proposal about asynchronous iteration, then here's what is interesting:

    We introduce a variation of the for-of iteration statement which iterates over async iterable objects. Async for-of statements are only allowed within async functions and async generator functions

    That is, our object should be not just iterable , but “asyncIterable” through the new well-known symbol Symbol.asyncIterator and, in our case, already an asynchronous generator function:

    let iter = {
      [Symbol.asyncIterator]: async function* iterf() {
        let fs = ['/1', '/2', '/3'];
        for (const req in fs) {
          yield await fetch(req);
        }
      }
    };
    

    How then does it work on a regular iterator and generator? Yes, just implicitly, like so much more in this language. This for-await-of is tricky: if the object is only iterable , then when iterating asynchronously, it "converts" the object to asyncIterable by wrapping the elements (if necessary) in Promise with the expectation of resolution. He spoke in more detail in an article by Axel Rauschmayer .

    Probably, through Symbol.asyncIterator it will still be more correct, since we explicitly made an asyncIterable object for our asynchronous iteration through for-await-of, while leaving the opportunity, if necessary, to supplement the object with a regular iterator for for-of . If you want to read something useful and sufficient in one article about asynchronous iterations in JavaScript, then here it is !

    Asynchronous for-of is still partially in draft, but it is already supported by modern browsers (except Edge) and Node.js from 10.x. If this bothers someone, you can always write your own small polyphile for a chain of promises, for example, for an iterable object:

    const chain = (promises, callback) => new Promise(resolve => function next(it) {
        let i = it.next();
        i.done ? resolve() : i.value.then(res => {
          callback(res);
          next(it);
        });
      }(promises[Symbol.iterator]())
    );
    ;(async function() {
      let iter = { /* iterable */ };
      await chain(iter, console.log);
      console.log('done');
    })();
    

    In this and such ways, we figured out sending requests and processing responses in turn. But in this problem there is one more small but annoying problem ...

    Mindfulness test


    We were so carried away by all this asynchronism that, as often happens, we lost sight of one small detail. Are those requests sent by our script? Let's see the network : But our numbers are 1, 2, 3. As if a decrement had occurred. Why is that? Just in the source code of the task there is another problem with iteration, here:

    GET https://www.example.com/0
    GET https://www.example.com/1
    GET https://www.example.com/2



    let fs = ['/1', '/2', '/3'];
    for (const req in fs) {
      yield fetch(req);
    }
    

    Here a for-in is used , which instead of array values ​​bypasses its enumerated properties: and these are the indices of elements from 0 to 2. The fetch function still leads them to strings and, despite the absence of a slash before (this is no longer path ), it resolves relatively URL of the current page. To fix is ​​much easier than to notice. Two options:

    let fs = ['/1', '/2', '/3'];
    for (const req of fs) {
      yield fetch(req);
    }
    let fs = ['/1', '/2', '/3'];
    for (const req in fs) {
      yield fetch(fs[req]);
    }
    

    In the first, we used the same for-of to iterate over the values ​​of the array, in the second - access to the array element by index.

    Motivation


    We considered 3 solutions: 1) through await in the for-of body , 2) through for-await-of, and 3) through our polyfile (recursive function, pipe pipeline , etc.). It is curious that these options divided the conference participants approximately equally and no obvious favorite was revealed. In large projects, for such real tasks, a reactive library (for example, RxJS ) is usually used , but it is worth remembering the modern native features of a language with an asynchronous nature.

    About half of the participants did not notice errors in the iteration over the list of resources, which is also an interesting observation. Focusing on a non-trivial but obvious problem, we can easily skip this seemingly trifle, but with potential serious consequences.

    Problem 3 ~ Factor 19th


    How many times in the record of the number 2019! (factorial from 2019) does the number 19 occur? Along with the answer, provide a JavaScript solution.

    Research problem


    The problem is on the surface: we need a record of a very large number to find in it the number of all occurrences of the substring “19”. Solving the problem on number 's, we very quickly run into Infinity (after 170) and did not get anything. In addition, the format for representing numbers float64 guarantees the accuracy of only 15-17 characters, and we need to get not only a complete, but also an accurate record of the number. Hence, the main difficulty is to determine the structure for the accumulation of this large number.

    Big integers


    If you follow the innovations of the language, the task is solved simply: instead of the type number, you can use the new type BigInt (stage 3) , which allows you to work with arbitrary precision numbers. With the classic recursive function for calculating factorial and finding matches via String.prototype.split, the first solution looks like this:

    const fn = n => n > 1n ? n * fn(n - 1n) : 1n;
    console.log(fn(2019n).toString().split('19').length - 1); // 50
    

    However, two thousand function calls on the stack can already be dangerous . Even if you bring the solution to tail recursion , then Tail call optimization still only supports Safari. The factorial problem here is more pleasant to solve through an arithmetic cycle or Array.prototype.reduce :

    console.log([...Array(2019)].reduce((p, _, i) => p * BigInt(i + 1), 1n).toString().match(/19/g).length); // 50
    

    This may seem like an insanely long procedure. But this impression is deceptive. If you estimate, then we just need to spend a little more than two thousand multiplications. At i5-4590 3.30GHz in chrome, the problem is solved on average in 4-5ms (!).

    Another option for finding matches in a string with the result of a calculation is String.prototype.match by regular expression with the global search flag: / 19 / g .

    Big arithmetic


    But what if we don't have this BigInt (and libraries too) yet ? In this case, you can do the long arithmetic yourself. To solve the problem, it is enough for us to implement only the function of multiplying large by small (we multiply by numbers from 1 to 2019). We can hold a large number and the result of multiplication, for example, in the line:

    /**
     * @param {string} big
     * @param {number} int
     * @returns {string}
     */
    const mult = (big, int) => {
      let res = '', carry = 0;
      for (let i = big.length - 1; i >= 0; i -= 1) {
        let prod = big[i] * int + carry;
        res = prod % 10 + res;
        carry = prod / 10 | 0;
      }
      return (carry || '') + res;
    }
    console.log([...Array(2019)].reduce((p, _, i) => mult(p, i + 1), '1').match(/19/g).length); // 50
    

    Here we simply multiply the column in bits from the end of the line to the beginning, as we were taught at school. But the solution already requires about 170ms.

    We can improve the algorithm somewhat by processing more than one digit in a number record at a time. To do this, we modify the function and at the same time go to the arrays, so as not to mess around with the lines every time:

    /**
     * @param {Array} big
     * @param {number} int
     * @param {number} digits
     * @returns {Array}
     */
    const mult = (big, int, digits = 1) => {
      let res = [], carry = 0, div = 10 ** digits;
      for (let i = big.length - 1; i >= 0 || carry; i -= 1) {
        let prod = (i < 0 ? 0 : big[i] * int) + carry;
        res.push(prod % div);
        carry = prod / div | 0;
      }
      return res.reverse();
    }
    

    Here, large numbers are represented by an array, each element of which stores information about digits digits from the number record, using number . For example, the number 2016201720182019 with digits = 3 will be represented as: Converting to a line before a join, you need to remember the leading zeros. The factor function returns the calculated factorial by a string, using the mult function with the specified number of processed digits at a time in the "massive" representation of the number when calculating:

    '2|016|201|720|182|019' => [2,16,201,720,182,19]



    const factor = (n, digits = 1) => 
      [...Array(n)].reduce((p, _, i) => mult(p, i + 1, digits), [1])
        .map(String)
        .map(el => '0'.repeat(digits - el.length) + el)
        .join('')
        .replace(/^0+/, '');
    console.log(factor(2019, 3).match(/19/g).length); // 50
    

    The "knee-length" implementation through arrays turned out to be faster than through strings, and with digits = 1 it calculates the answer already on average in 90ms, digits = 3 in 35ms, digits = 6 in just 20ms. However, remember that increasing the number of digits, we are approaching a situation where multiplying number by number “under the hood” may be outside the safe MAX_SAFE_INTEGER . You can play with it here . What is the maximum digits value we can afford for this task?

    The results are already quite indicative, BigInt is really pretty quick:



    Motivation


    It's cool that 2/3 of the conference participants used the new BigInt type in the solution (someone admitted that this was the first experience). The remaining third of the solutions contained their own implementations of long arithmetic on strings or arrays. Most of the implemented functions multiplied large numbers by large ones, when for a solution it was enough to multiply by a "small" number and spend a little less time. Okay task, do you already use BigInt in your projects?

    Acknowledgments


    These two days of the conference were very full of discussions and learning something new. I would like to thank the program committee for the next unforgettable conference and all the participants for their unique networking and good mood.

    Also popular now: