Διαχείρηση stack σε Node.js όταν γίνετε αναδρομή

[PC_MAGAS]

Όπως ρωτώ και στο stackoverflow θέλω να εκτελέσω έναν αναδρομικό υπολογισμό (που θεωρείτε καλύτερο σε Node.js και javascript αντί χρήση loop) όμως αναδρομή = συνεχή αύξηση του stack από όσο γνωρίζω έτσι θεωρώντας ότι έχουμε την εξής μέθοδο:

const nextOdd = (num, callback) => {
  const next= num+1;
  if(next % 2){
   return callback(next)
  } else {
    nextOdd(num,callback);
  }
}

Σκεπτικά  να εκτελώ είτε την callback είτε την αναδρομική κλήση της function ασύγχρονα  λόγο ότι η μέθοδος θα κάνει return πρωτού κληθεί η επόμενη αναδρομή.

const nextOdd = (num, callback) => {
  const next= num+1;
  if(next % 2){
   return process.nexctTick(() =>  callback(next) );
  } else {
    return process.nextTick(() => nextOdd(num, callback) );
  }
}

Και θα μου πείτε "Μα γιατί φίλε pc_magas να κάνεις αναδρομή" , well η javascript δεν τα πάει καλά με τις λούπες και cpu itensive πράγματα, έτσι εάν θες να εκτελέσεις μια σειρά taylor σε node.js ίσως η αναδρομή να αποτελεί μονόδρομο.

 

Παρόλα αυτά η απορία μου είναι καταφέρνω να μικρύνω το μέγεθος της stack με το να κάνω return και asyncronous call η όχι;

Επεξ/σία 4 Ιανουαρίου 2019 από PC_MAGAS

[παπι]

Θα κανεις async αναδρομη για να γλιτωσεις το "βαρος" της for; Δε ξερω γιατι θες να πας αναδρομη απο την ωρα που η for ειναι οτι πιο κοντα υπαρχει στο μαθηματικο συνολο (Σ)

[albNik]

Αυτό που καταλαβαίνω είναι ότι θες να σπάσεις ένα βαρύ υπολογισμό (μια πολύ μεγάλη for) ώστε να είναι responsive το event loop.
Μπορείς απλά να κανεις κάποια 'διαλειματα' από τη for (π.χ. κάθε 1000 iterations).

for( i = 0; i < 100000000000; i++)
{
   if(i% 1000 == 0)
     process.nextTick();
    ....
    ....
}

 

[PC_MAGAS]

Αλλά απ' ευθείας απάντηση στο τελικά μικραίνω την stack δεν λαμβάνω.

@παπι Προσπαθώ να κάνω όπως λέει ο @albNik το event loop ποιο responsive σε βαρύς υπολογισμούς. Ένας τρόπος είναι η αναδρομή με το bonus ότι έχω ποιο ευανάγνωστο κώδικα. Αλλά δεν ξέρω εάν κάνω asyncCall και return εάν θα καταφέρω να μανατζάρω το stack σε λογικά πλαίσια. Δλδ με return να βγάζω την υπάρχουσα function από το stack και να βάζω στο event loop την κλήση της επόμενης.

 

33 λεπτά πριν, albNik είπε

Αυτό που καταλαβαίνω είναι ότι θες να σπάσεις ένα βαρύ υπολογισμό (μια πολύ μεγάλη for) ώστε να είναι responsive το event loop.
Μπορείς απλά να κανεις κάποια 'διαλειματα' από τη for (π.χ. κάθε 1000 iterations). 

for( i = 0; i < 100000000000; i++)
{
   if(i% 1000 == 0)
     process.nextTick();
    ....
    ....
}

Μου μυρίζει μη καθαρό κώδικα που εάν η ayscronous αναδρομή έχει ποιο μικρά κομματάκια function με την προϋπόθεση ότι ισχύει η υπόθεσή μου ίσως να μπορώ να έχω καθαρό κώδικα, responsive event loop και ποιο μικρά maintainable κομμάτια κώδικα.

Ο αντίποδας βέβαια είναι ότι θέλει κάθε function σε δικιά της variable για να γλιτώνεις το callback hell.

Επεξ/σία 31 Δεκεμβρίου 2018 από PC_MAGAS

[alou]

Στις 31/12/2018 στις 1:56 ΜΜ, PC_MAGAS είπε

Παρόλα αυτά η απορία μου είναι καταφέρνω να μικρύνω το μέγεθος της stack με το να κάνω return και asyncronous call η όχι;

Εξ'ορισμού, όχι. Η ασύγχρονη κλήση, θα στείλει ένα function στο queue που αναλογεί και το event loop, εφόσον δεν γίνεται κάτι στο main execution ή σε άλλο queue που προηγείται, θα την βάλει στο stack. Τώρα αν μεσολαβούν άλλα πράγματα μπορεί προφανώς να συμβεί οτιδήποτε.

Γιατί ακριβώς θες να μικρύνεις το μέγεθος του stack? το πιθανότερο συμπέρασμα θα ήταν να αποφύγεις maximum call stack exceeded. Aν αυτός είναι ο λόγος, μια και το tail call optimisation υπάρχει μόνο στο σπεκ, ξέχασε το recursion ή ψάξε παραδείγματα με thunk / tramboline γιατί καμία ασύγχρονη λύση, είτε λέγεται nextTick, setTimeout, Promise.resolve ... δεν θα σου εξασφαλίσει κάτι τέτοιο. 

TCO: http://2ality.com/2015/06/tail-call-optimization.html

Maximum call stack limit: http://2ality.com/2014/04/call-stack-size.html

wtf is tramboline: http://raganwald.com/2013/03/28/trampolines-in-javascript.html

[PC_MAGAS]

Στις 2/1/2019 στις 7:08 ΜΜ, alou είπε

Εξ'ορισμού, όχι. Η ασύγχρονη κλήση, θα στείλει ένα function στο queue που αναλογεί και το event loop, εφόσον δεν γίνεται κάτι στο main execution ή σε άλλο queue που προηγείται, θα την βάλει στο stack. Τώρα αν μεσολαβούν άλλα πράγματα μπορεί προφανώς να συμβεί οτιδήποτε. 

Γιατί ακριβώς θες να μικρύνεις το μέγεθος του stack? το πιθανότερο συμπέρασμα θα ήταν να αποφύγεις maximum call stack exceeded. Aν αυτός είναι ο λόγος, μια και το tail call optimisation υπάρχει μόνο στο σπεκ, ξέχασε το recursion ή ψάξε παραδείγματα με thunk / tramboline γιατί καμία ασύγχρονη λύση, είτε λέγεται nextTick, setTimeout, Promise.resolve ... δεν θα σου εξασφαλίσει κάτι τέτοιο.  

TCO: http://2ality.com/2015/06/tail-call-optimization.html

Maximum call stack limit: http://2ality.com/2014/04/call-stack-size.html

wtf is tramboline: http://raganwald.com/2013/03/28/trampolines-in-javascript.html

Νομίζω σηκώνει μια απάντηση (με code sample) στο: https://stackoverflow.com/questions/53986932/is-the-way-calling-the-nextodd-method-will-reduce-the-stack-size  και ένα link στην απάντηση σου εδώ λόγο ότι θα προσφέρει χρήσιμη γνώση στο σύνολο των προγραμματιαστών. (Σύν ότι θα λάβεις και θα λάβω reputation points, άκρα σημαντικό για εμένα 😛 .)

Επεξ/σία 3 Ιανουαρίου 2019 από PC_MAGAS

[solarpower]

Μπορείς να αποφύγεις την αναδρομή με μια στοίβα όπου θα παίζει το ρόλο του stack, για να βάζεις ενδιάμεσα αποτελέσματα. Γενικά πάντως δεν γίνεται να έχεις ένα πρόγραμμα όπου περιμένεις μισή ώρα να τελειώσει ο υπολογισμός, και στο μεταξύ να θέλεις να σου  δίνει χρόνο να κάνεις και κάτι άλλο σε αυτήν! Δηλαδή τι θα κάνεις, θα σου βγάλει ένα παιχνίδι να παίζεις στην ώρα της αναμονής;

[PC_MAGAS]

53 λεπτά πριν, solarpower είπε

Μπορείς να αποφύγεις την αναδρομή με μια στοίβα όπου θα παίζει το ρόλο του stack, για να βάζεις ενδιάμεσα αποτελέσματα. Γενικά πάντως δεν γίνεται να έχεις ένα πρόγραμμα όπου περιμένεις μισή ώρα να τελειώσει ο υπολογισμός, και στο μεταξύ να θέλεις να σου  δίνει χρόνο να κάνεις και κάτι άλλο σε αυτήν! Δηλαδή τι θα κάνεις, θα σου βγάλει ένα παιχνίδι να παίζεις στην ώρα της αναμονής; 

Well η javascript κατά spec ενθαρρύνει αναδρομή αντί λούπας ακόμα μέσω process nextTick μπορώ να εκτελέσω ασύγχρονη αναδρομή δίνοντας προτεραιότητα σε άλλα events. Ακόμα μέσω process.nexTick εφόσον λαμβάνει παράμετρο μια function μπορώ να περάσω μια callback για ενδιάμεσες τιμές πχ:

 

const nextOdd = (num, callback, intermediateCallback) => {
  const next= num+1;
  if(next % 2){
   return process.nexctTick(() =>  callback(next) );
  } else {
    return process.nextTick(() => {intermediateCallback(next); nextOdd(num, callback););
  }
}

Όπως βλέπεις λαμβάνω ενδιάμεσες τιμές μέσω callback. Ακόμη σκέψου ότι η node.js  και η javascript είναι μανούλι σε ασύγχρονα ή και eventfull πράγματα αντί ένα μεγάλο σύχρονο loop. Ακόμη δε το πέρας μιας επεξεργασίας μπορώ μέσω callback ή και event να το κάνω trigger. Άρα ναι μεν η προσέγγιση μου επηρεάζει στοίβα και χρόνο εκτέλεσης + μνήμη ΑΛΛΑ κερδίζω responsiveness της εφαρμογής χωρίς να μπλοκάρω άλλα events με το να δίνω προτεραιότητα σε άλλα events από το event loop.

Ακόμα και στο trampoline example αποφεύγει loops έαν δεις και κάνει κάτι ποιο κοντά σε recursion. Συνδύασε το με async για το responsiveness ΜΠΟΥΜ problem solved.

Εάν είναι ΠΑΡΑ πολυ CPU Itensive αυτό που κάνεις τότε είτε κάνεις C++ Module και κρύβεις από κάτω Threads, Cuda, OpenCl, Special Hardware Calling code, Assembly linked Code, Chuck Norris Optimized Code κλπ κλπ ή σε ποιο ελαφρές ανάγκες πας σε λύσεις όπως  αυτή..

[solarpower]

το πρόβλημα είναι ότι σκέφτεσαι πως η callback θα περιμένει σε stateless περιβάλλον, αλλά και αυτή όπως και ο υπολογισμός σου γίνονται σε ένα μεταβαλλόμενο περιβάλλον, άρα θα έχεις θέματα συγχρονισμού. Η λύση μάλλον είναι να βάλεις ένα timer να σου εκτελεί τον υπολογισμό σε δόσεις. Να σπάσεις το for σε μικρότερα. Έτσι θα βάλεις και το callback να είναι ανεξάρτητο, να περιμένει δηλαδή και αυτό ένα event για να κάνει ό,τι έχει.

[PC_MAGAS]

@solarpower Γι αυτό παίζεις με Immutable (βέβαια στο παράδειγμα δεν το λαμβάνω καν υπόψιν) με το να καταστρέφεις και να δημιουργείς αντικείμενα. Αν μιλούσα για C, C++, Java τότε ναι θα έλεγα απέφυγε recursion όσο μπορείς όμως σε javascript hmm καλύτερα recursion ή λύσεις τύπου trampoline.

 

Ακόμη εάν η επεξεργασία είναι ασύγχρονη τότε πώς θα το τρέξεις σε λούπα σε javascript;

Επεξ/σία 4 Ιανουαρίου 2019 από PC_MAGAS

[k33theod]

Μήπως αυτό που θες είναι ένας generator. 

Generators compute their yielded values on demand, which allows them to efficiently represent sequences that are expensive to compute, or even infinite sequences as demonstrated above.

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Iterators_and_Generators

 

[ajaxmonkey4hire]

Στις 31/12/2018 στις 5:56 ΠΜ, PC_MAGAS είπε

Και θα μου πείτε "Μα γιατί φίλε pc_magas να κάνεις αναδρομή" , well η javascript δεν τα πάει καλά με τις λούπες και cpu itensive πράγματα, έτσι εάν θες να εκτελέσεις μια σειρά taylor σε node.js ίσως η αναδρομή να αποτελεί μονόδρομο.

Javascript τα πάει μια χαρά με loops μια for ή while loop σου την κάνει την δουλειά. Το πρόβλημα προκύπτει όταν έχεις πολλούς υπολογισμούς μέσα στην loop διότι μιας και η V8  engine είναι single threaded θα σου μπλοκάρει την εφαρμογή.

Η σωστή λύση σε τέτοιες περιπτώσεις είναι να πάρεις την συνάρτηση που κάνει πολλούς υπολογισμούς μέσα στην loop και να την βάλεις μέσα σε ένα child process ώστε και να μην μπλοκάρεται η εφαρμογή σου και να αξιοποιείται καλύτερα το multicore environment στο οποίο, κατά πάσα πιθανότητα, την τρέχεις.

άσε που δεν προκύπτει το τι είναι ακριβώς αυτό που θέλεις να κάνεις απο τον κώδικα που παρέθεσες.

Επεξ/σία 6 Ιανουαρίου 2019 από ajaxmonkey4hire

[ajaxmonkey4hire]

const nextOdd = (num, cb)=>{
	var next = num+1;
	
	if ( next%2 && next>10  ){
		cb(next);
	}else{
		process.nextTick(function(){nextOdd(next, cb)});
	}	
}


nextOdd(0, (num)=>{console.log('All done: '+num);})

Αυτό σου δινει ον πρώτο μονό μεγαλύτερο του δέκα. Ανακαλείς την nextOdd μέχρι να βρεθεί και μετά καλείς την cb και βγαίνεις από την διαδικασία. Αυτό ζητάς;

[PC_MAGAS]

Βασικά αναζητούσα κάτι ποιο generic και έθεσα το παράδειγμα σαν example στο πως να διαχειριζόμαστε Large Data Iterations με αναδρομή.

[ajaxmonkey4hire]

2 ώρες πριν, PC_MAGAS είπε

Βασικά αναζητούσα κάτι ποιο generic και έθεσα το παράδειγμα σαν example στο πως να διαχειριζόμαστε Large Data Iterations με αναδρομή.

Τρέχεις αυτό:

const nextOdd = (num, cb)=>{
	var next = num+1;
	
	if ( next%2 && next>100000000  ){
		cb(next);
	}else{
		process.nextTick(function(){nextOdd(next, cb)});
	}	
}


nextOdd(0, (num)=>{console.log('All done: '+num);})

Και τρέχεις το top σε δεύτερη κονσόλα. Θα δεις ότι η χρήση μνήμης παραμένει σταθερή, οπότε δεν μεγαλώνει το stack. Αλλά η χρήση CPU παει στο 100% οπότε δεν είναι ούτε non blocking. Το τελευταίο πετυχαίνεται αν αντικαταστήσεις το process.nextTick με setTimeout ή με child process.

Πέρα από αυτά η nodejs docu λέει ξεκάθαρα:

It is very important for APIs to be either 100% synchronous or 100% asynchronous.

 

Επεξ/σία 7 Ιανουαρίου 2019 από ajaxmonkey4hire