Vraag Voeren Immutable.js of Lazy.js korte-snelheidsfusie uit?


Laat me eerst definiëren wat er is kortere fusie voor degenen onder u die het niet weten. Overweeg de volgende arraytransformatie in JavaScript:

var a = [1,2,3,4,5].map(square).map(increment);

console.log(a);

function square(x) {
    return x * x;
}

function increment(x) {
    return x + 1;
}

Hier hebben we een array, [1,2,3,4,5], waarvan de elementen eerst gekwadrateerd zijn, [1,4,9,16,25]en vervolgens verhoogd [2,5,10,17,26]. Daarom hebben we de tussenliggende array niet nodig [1,4,9,16,25], we creëren het nog steeds.

Short-cut fusion is een optimalisatietechniek die intermediaire datastructuren kan verwijderen door een aantal functieaanroepen samen te voegen tot één. Zo kan bijvoorbeeld korte-snij-fusie op de bovenstaande code worden toegepast om te produceren:

var a = [1,2,3,4,5].map(compose(square, increment));

console.log(a);

function square(x) {
    return x * x;
}

function increment(x) {
    return x + 1;
}

function compose(g, f) {
    return function (x) {
        return f(g(x));
    };
}

Zoals u kunt zien, zijn de twee gescheiden map oproepen zijn samengevoegd tot een single map bel door het samenstellen van de square en increment functies. Daarom is de tussenliggende array niet gemaakt.


Nu begrijp ik dat bibliotheken leuk vinden Immutable.js en Lazy.js emuleren luie evaluatie in JavaScript. Luie evaluatie betekent dat resultaten alleen worden berekend als dat nodig is.

Overweeg bijvoorbeeld de bovenstaande code. Hoewel wij square en increment elk element van de array, maar we hebben misschien niet alle resultaten nodig.

Stel dat we alleen de eerste 3 resultaten willen. Met Immutable.js of Lazy.js kunnen we de eerste 3 resultaten krijgen, [2,5,10], zonder de laatste 2 resultaten te berekenen, [17,26], omdat ze niet nodig zijn.

Luie evaluatie vertraagt ​​echter alleen de berekening van de resultaten tot deze nodig is. Intermediaire gegevensstructuren worden niet verwijderd door functies te fuseren.

Om dit duidelijk te maken, overweeg dan de volgende code die luie evaluatie emuleert:

var List = defclass({
    constructor: function (head, tail) {
        if (typeof head !== "function" || head.length > 0)
            Object.defineProperty(this, "head", { value: head });
        else Object.defineProperty(this, "head", { get: head });

        if (typeof tail !== "function" || tail.length > 0)
            Object.defineProperty(this, "tail", { value: tail });
        else Object.defineProperty(this, "tail", { get: tail });
    },
    map: function (f) {
        var l = this;

        if (l === nil) return nil;

        return cons(function () {
            return f(l.head);
        }, function () {
            return l.tail.map(f);
        });
    },
    take: function (n) {
        var l = this;

        if (l === nil || n === 0) return nil;

        return cons(function () {
            return l.head;
        }, function () {
            return l.tail.take(n - 1);
        });
    },
    mapSeq: function (f) {
        var l = this;
        if (l === nil) return nil;
        return cons(f(l.head), l.tail.mapSeq(f));
    }
});

var nil = Object.create(List.prototype);

list([1,2,3,4,5])
    .map(trace(square))
    .map(trace(increment))
    .take(3)
    .mapSeq(log);

function cons(head, tail) {
    return new List(head, tail);
}

function list(a) {
    return toList(a, a.length, 0);
}

function toList(a, length, i) {
    if (i >= length) return nil;

    return cons(a[i], function () {
        return toList(a, length, i + 1);
    });
}

function square(x) {
    return x * x;
}

function increment(x) {
    return x + 1;
}

function log(a) {
    console.log(a);
}

function trace(f) {
    return function () {
        var result = f.apply(this, arguments);
        console.log(f.name, JSON.stringify([...arguments]), result);
        return result;
    };
}

function defclass(prototype) {
    var constructor = prototype.constructor;
    constructor.prototype = prototype;
    return constructor;
}

Zoals je ziet, worden de functie-aanroepen doorschoten en worden alleen de eerste drie elementen van de array verwerkt, wat bewijst dat de resultaten inderdaad lui zijn berekend:

square [1] 1
increment [1] 2
2
square [2] 4
increment [4] 5
5
square [3] 9
increment [9] 10
10

Als luie evaluatie niet wordt gebruikt, zou het resultaat zijn:

square [1] 1
square [2] 4
square [3] 9
square [4] 16
square [5] 25
increment [1] 2
increment [4] 5
increment [9] 10
increment [16] 17
increment [25] 26
2
5
10

Echter, als u de broncode ziet dan elke functie list, map, take en mapSeq geeft een tussenproduct als resultaat List data structuur. Er wordt geen kortere fusie uitgevoerd.


Dit brengt me bij mijn hoofdvraag: werken bibliotheken zoals Immutable.js en Lazy.js kortere fusion?

De reden waarom ik vraag is omdat ze volgens de documentatie "blijkbaar" doen. Ik ben echter sceptisch. Ik heb mijn twijfels of ze daadwerkelijk short-cut fusion uitvoeren.

Dit is bijvoorbeeld afkomstig van de README.md bestand van Immutable.js:

Immutable biedt ook een lui Seq, waardoor efficiënte koppeling van verzamelmethoden zoals map en filter zonder tussentijdse representaties te creëren. Maak er een paar Seq met Range en Repeat.

Dus de ontwikkelaars van Immutable.js beweren dat hun Seq datastructuur maakt efficiënte ketenvorming van verzamelmethoden zoals map en filter  zonder tussentijdse representaties te creëren (d.w.z. ze voeren korte-snij-fusie uit).

Ik zie ze echter niet in hun code overal. Misschien kan ik het niet vinden omdat ze ES6 gebruiken en mijn ogen zijn niet al te bekend met de ES6-syntaxis.

Verder in hun documentatie voor Lazy Seq zij vermelden:

Seq beschrijft een luie operatie, waardoor ze efficiënt gebruik van alle itereerbare methoden (zoals map en filter).

Seq is onveranderlijk - Zodra een Seq is gemaakt, kan deze niet worden gewijzigd, toegevoegd aan, herschikt of anderszins worden gewijzigd. In plaats daarvan zal elke mutatieve methode die een Seq wordt aangeroepen een nieuwe Seq retourneren.

Seq is lui - Seq doet zo weinig werk als nodig is om te reageren op elke methode aanroep.

Dus het is vastgesteld dat Seq is inderdaad lui. Er zijn echter geen voorbeelden om dat te laten zien tussentijdse representaties worden inderdaad niet gemaakt (wat ze beweren te doen).


Verder naar Lazy.js hebben we dezelfde situatie. Gelukkig schreef Daniel Tao een blogpost over hoe Lazy.js werkt, waarin hij vermeldt dat Lazy.js in zijn hart eenvoudig functioneert als compositie. Hij geeft het volgende voorbeeld:

Lazy.range(1, 1000)
    .map(square)
    .filter(multipleOf3)
    .take(10)
    .each(log);

function square(x) {
    return x * x;
}

function multipleOf3(x) {
    return x % 3 === 0;
}

function log(a) {
    console.log(a);
}
<script src="https://rawgit.com/dtao/lazy.js/master/lazy.min.js"></script>

Hier de map, filter en take functies produceren gemiddeld MappedSequence, FilteredSequence en TakeSequence voorwerpen. Deze Sequence objecten zijn in wezen iterators, waardoor er geen tussenliggende arrays nodig zijn.

Wat ik echter wel begrijp, is dat er nog steeds geen kortere fusie plaatsvindt. De tussenliggende arraystructuren worden eenvoudig vervangen door een tussenproduct Sequence structuren die niet gefuseerd zijn.

Ik zou het mis hebben, maar ik geloof dat uitdrukkingen zoals Lazy(array).map(f).map(g) produceer twee gescheiden MappedSequence objecten waarin de eerste MappedSequence object voert zijn waarden naar de tweede, in plaats van de tweede die de eerste vervangt door de taak van beide te doen (via functiesamenstelling).

TLDR: Voeren Immutable.js en Lazy.js inderdaad short-cut fusion uit? Voor zover ik weet ontdoen ze zich van tussenliggende reeksen door luie evaluatie te emuleren via sequentieobjecten (dat wil zeggen iteratoren). Ik geloof echter dat deze iteratoren zijn geketend: een iterator die zijn waarden lui doorgeeft aan de volgende. Ze zijn niet samengevoegd tot een enkele iterator. Daarom "elimineren ze geen tussentijdse representaties". Ze transformeren arrays alleen in objecten met constante ruimtesequenties.


29
2017-12-17 15:49


oorsprong


antwoorden:


Ik ben de auteur van Immutable.js (en een fan van Lazy.js).

Doet Lazy.js en Immutable.js's Seq korte-snij-fusion? Nee, niet precies. Maar ze verwijderen tussentijdse weergave van bewerkingsresultaten.

Short-cut fusion is een code compilatie / transpilatie techniek. Uw voorbeeld is goed:

var a = [1,2,3,4,5].map(square).map(increment);

Transpiled:

var a = [1,2,3,4,5].map(compose(square, increment));

Lazy.js en Immutable.js zijn geen transpilers en zullen de code niet opnieuw schrijven. Het zijn runtime-bibliotheken. Dus in plaats van korte-snij-fusie (een compilertechniek) gebruiken ze een itereerbare compositie (een runtime-techniek).

Je antwoordt dit in je TLDR:

Voor zover ik weet, ontdoen ze zich van tussenliggende arrays door lui te emuleren   evaluatie via sequentieobjecten (dat wil zeggen iteratoren). Ik geloof echter   dat deze iterators zijn geketend: één iterator die zijn waarden voedt   lui naar de volgende. Ze zijn niet samengevoegd tot een enkele iterator. Vandaar   ze "elimineren geen tussentijdse representaties". Alleen zij   transformeer arrays in objecten met constante ruimtesequentie.

Dat is precies goed.

Laten we uitpakken:

Arrays slaan tussentijdse resultaten op bij het ketenen:

var a = [1,2,3,4,5];
var b = a.map(square); // b: [1,4,6,8,10] created in O(n)
var c = b.map(increment); // c: [2,5,7,9,11] created in O(n)

Short-cut fusion transpilation creëert tussentijdse functies:

var a = [1,2,3,4,5];
var f = compose(square, increment); // f: Function created in O(1)
var c = a.map(f); // c: [2,5,7,9,11] created in O(n)

Intersamenstelling maakt tussenliggende iterables:

var a = [1,2,3,4,5];
var i = lazyMap(a, square); // i: Iterable created in O(1)
var j = lazyMap(i, increment); // j: Iterable created in O(1)
var c = Array.from(j); // c: [2,5,7,9,11] created in O(n)

Merk op dat met behulp van een iterabele samenstelling, we geen opslag van tussentijdse resultaten hebben gecreëerd. Wanneer deze bibliotheken zeggen dat ze geen tussenliggende representaties creëren - wat ze bedoelen, is precies wat in dit voorbeeld wordt beschreven. Er is geen datastructuur gemaakt met de waarden [1,4,6,8,10].

Natuurlijk sommige tussentijdse weergave is gemaakt. Elke "luie" operatie moet iets teruggeven. Ze keren terug naar iterabel. Het maken van deze is extreem goedkoop en niet gerelateerd aan de grootte van de gegevens waarop wordt geopereerd. Merk op dat bij kortere fusie-transpilatie ook een tussenrepresentatie wordt gemaakt. Het resultaat van compose is een nieuwe functie. Functionele samenstelling (met de hand geschreven of het resultaat van een korte-cut fusie-compiler) is zeer gerelateerd aan de Itereerbare samenstelling.

Het doel van het verwijderen van tussentijdse representaties is de prestaties, vooral met betrekking tot het geheugen. In itereerbare samenstelling is een krachtige manier om dit te implementeren en vereist niet de overhead die code van een optimaliserende compiler ontleedt en herschrijft die in een runtime-bibliotheek niet op zijn plaats zou zijn.


appx:

Dit is wat een eenvoudige implementatie van lazyMap zou kunnen lijken op:

function lazyMap(iterable, mapper) {
  return {
    "@@iterator": function() {
      var iterator = iterable["@@iterator"]();
      return {
        next: function() {
          var step = iterator.next();
          return step.done ? step : { done: false, value: mapper(step.value) }
        }
      };
    }
  };
}

33
2017-12-17 19:01