Array of Strings and in and out of 'out of memory jail'

[espruino-discuss]

Posted at 2014-09-30 by @allObjects

Some pointers about the implementation of JS in Espruino is very welcome here. I provide an example from code I'm working on (Part of this conversation - including some helpful responses - began in http://forum.espruino.com/conversations/255757/ about GPS module and Extensions there of. It is now its own conversation for separation of concerns.)

I needed an array of strings - keys - for processing. So I created an array of strings in the source code and it got me quickly out of memory ( #outofmemory ) into the 'out of memory jail':

var keys = 
[ "key000"
, "key001"
, "key002"
, "key003"
// ...and many more...
, "keyNM9"
];
keys.forEach(function(k) { console.log(k); }

In a desperate move - with no real rational but just some guessing - I chose to group the keys w/ space as separator in fewer strings and apply some joining and splitting before processing to keep the same algorithm (because of performance) - and 'miraculously - it got me out of 'out of memory jail' (The joining-splitting with/by space is possible because the keys cannot include spaces):

var keys = 
[ "key000 key001 key002 key003 key004 key005 key006 key007 key008 key009"
, "key010 key011 key012 key013 key014 key015 key016 key017 key018 key019"
, "key020 key021 key022 key023 key024 key025 key026 key027 key028 key029"
// ...and many more...
, "keyNM0 keyNM1 keyNM2, keyNM3, keyNM4, keyNM5, keyNM6, keyNM7, keyNM8, keyNM9"
];
keys = keys.join(" ").split(" ");
keys.forEach(function(k) { console.log(k); }

There are several conversations out there about memory and out of memory and I reference them in this list:

1. http://forum.espruino.com/conversations/1724/ clearTimeout and WARNING: Out of memory while appending to array
2. http://forum.espruino.com/conversations/1578/
   GPS code/module/library leaking memory before 'satellite lock' occurs
3. http://forum.espruino.com/conversations/1192
   Out of memory?
4. [http://forum.espruino.com/conversations/1032](http://forum.espruino.com/conversations/1032/ Memory usage

But none of them can explain the following:

You may have notice in the above code the line keys = keys.join(" ").split(" ");

Even though I then kept/stored the joined-splitted-processed array, I was kept out of 'out of memory jail'. It must have to do something with how source code of arrays of string literals is pulled in and hold onto.

What is the 'somewhat puzzling' key-note to take from this experience?

PS: I had temporarily similar experience as mentioned in 2nd reference above, even though I used the fixed version of the .indexOf(...) - [1v70]. The issue showed in the GPS modules handleGPSLine when going for the decimal points with indexOf('.') in the lines received from the GPS receiver. Could it be that the .indexOf() String method is still a bit 'weak on its legs'. Having read about it I felt it had something to do by releasing the search argument string... but I may be totally wrong about ti. As said: it was temporary. Nevertheless, observing it cannot hurt.

[espruino-discuss]

Posted at 2014-10-01 by DrAzzy

(Mostly off-topic (as the topic is the bizzare behavior you're seeing) - are those the strings you're saving? I assume it's something more substantive than that - if that's all it is, you could write a very small function to get the string from the index number, and dispense with the array entirely)

[espruino-discuss]

Posted at 2014-10-01 by @allObjects

@drazzy, you are absolutely correct... the strings are way more substantial than algorithmic derivable values. The actual strings are shown in the code snippet below, which also includes the join-split and store operations in the ini() method. The 'KeyNMO'-thing was just a placeholder to imply that there are many of those - relatively short - strings. I did run out of memory when the strings in 2nd and 3rd block - which correlate - were less then half in count. The characters in the string are encoded values. The encoding is preliminary - but human readable and quick to interpret - and the encoded (unsigned) integer values are in ranges from 0 to 16, 32, and 96. I'm thinking of running them through a generator to compact them even more, and then use them as typed arrays. It would be interesting to elaborate on various implementations and the overall impact - not just in regard of the 'data and its structure', but also the dependent algorithms and their performance. For runtime - after initialization - the values are neededas individual addressable items. At one time I thought I could leave them as complete strings (joined) and access with .substr()... May be it will become possible after compacting them and then 'pay a bit more for it' while repeatedly extracting values. At a later time in the project I will be a more verbose about the strings' purposes.

;-)

var o = 
{ o: "some singleton object"
, bs: // borders "XY[Steps Right|steps left]...,..." filled polygons
["AACBC FADBD LaADA OADBD UACBC AECAC FEACcACcA IEGACcACc REAGACcAC UECAC"
,">HFDACe >LEadBa UHFDACe ULEadBa IKBAAcA NKBDACa JNEAE >NFDACe >REadBa"
,"FNADA RNADA UNFDACe UREadBa IQGACcACc ATCDACb FTDAD OTDAD UTCABcA ?WBAB"
,"FWACcAIAE IWGACcACc RWACeAIAC XWBAB >LAmMan LaNMano >RAKmAN L]NkALO"
]
, ns: // nodes to segs - [<..K..[..k..}]  - "xyG(oodie(s))h...(oriz)v...(ertic)"
["@@.(U E@.)V [email protected] N@.*X T@.+Y [email protected] @D.,[ ED.-\\ HD..] KD./ ND.0 QD.1^ TD.2_ YD.`"
,"@G.3 EG.a HG.4 KG.b NG.5c QG. TG.6d YG. HJ.7e KJ.8 NJ.9 QJ.f @M-: EM.;g HM.h"
,"QM.<i TM.=j YM- HP.>k QP.l @S.?m ES.@n HS.A KS.o NS.Bp QS.C TS.Dq YS.r @V.E"
,"BV.s EV.Ft HV.Gu KV.H NV.I QV.Jv TV.w WV.Kx YV. @Y.Ly BY.M EY. HY.N KY.z NY.O{"
,"QY. TY.P WY.Q YY.| @\\.R K\\.S N\\.T Y\\."
]
, ss: // segs - h[(..;..N..T] and v[V..a..s..|] - s(tart node)e(nd node)s(paces)
["<=D =>E ?@E @AD BCD CDB DEB EFB FGB GHB HID JKD LMB NOB PQD RSB STB TUB VWD"
,"WXB YZB Z[D \\]H ^_D _`B `aB bcB cdB deD fgA hiB ijB jkB klB lmB noB pqB qrB"
,"stB uvB wxB xyB z{J {|B |}J <BC =CC >EC ?FC @HC AIC BJB CKB DLB GOB HPB IQB"
,"KWE MSB NTB PzE RxB UyB W_E X\\B Y]B ZdE \\`B ]cB ^fB _hB ajB bkB dmB eoB"
,"gqB hrB isB lvB mwB nxB pzB t{B u|B y}B"
]
, ini: function() {
    (this.bs = this.bs.join(" ").split(" ")).forEach(function(b){
      // do some stuff with the 'encoded' b-order information... 
     });
    (this.ns = this.ns.join(" ").split(" ")).forEach(function(n){
      // do stuff with the 'encoded' n-ode information...
     });
    (this.ss = this.ss.join(" ").split(" ")).forEach(function(s){
      // do stuff with the 'encoded' s-egment information...
     });
};
o.ini();

[gfwilliams]

Posted at 2014-10-01 by @gfwilliams

Hi, I think in this case the issue might be that you're defining the keys inside the function. This means that the function itself is using a lot of memory (probably more so that the actual data because of the padding). You could check using E.getSizeOf(fn)

Then, when you run that function you've got two copies of the data - one in the source and one that had just been created.

If you defined the data in the root scope then Espruino would discard the source after executing it, leaving you with just one copy. It'll be faster too.

You'll find that storing a few large strings (like you're doing) is probably more efficient than a small array of strings. You could save even more memory by just iterating over the array rather than joining it into a large string first too.

Having said that, using large chunks of data like this really hammers home just how small 48kB is. Microcontrollers just have fairly limited resources, and you have to adjust your coding style to fit within their limits.

[gfwilliams]

Posted at 2014-10-01 by @gfwilliams

Just to add, have you seen these pages:

• http://www.espruino.com/Performance
• http://www.espruino.com/Internals

They might give you some hints about how the interpreter works...

[espruino-discuss]

Posted at 2014-10-02 by cephdon

If we had the ability to do a relative seek in a file, or the ability to move to an absolute position (forward and backward) in the file, then we could build a relatively unlimited (from the perspective of memory) key value store (or simple db). It's easier if it's relative, though.

Basically, you store in a file(for each entry):
Offset to the beginning of the next entry, offset to the beginning of the previous entry, key, data. (Or, size of this entry, size of previous entry, key, data. It's the same thing when relative)
It could be line delimited, or not.
In any case, you could easily binary search the database for your data, assuming you sort it at insertion time.
Then, when that is done, you only keep the data you want in memory and leave the rest saved to disk.

It might not be as fast as an in memory array, but with a 32GB sd card, you could store and search much more than the memory available.

[espruino-discuss]

Posted at 2014-10-02 by @allObjects

I'm recalling having read them when I came across Espruino the very first time - even before having had a board in hand. I glanced over it when replacing my first [1v67] with [1v70] with enhanced memory management. I though did not pay as much attention until now, after encountered out of memory.

(Nur) die eigene Erfahrung hat den Vorzug voelliger Gewissheit.

(Only) the very own experience has the advantage of absolute doubtlessness.

Arthur Schopenhauer - 1788-1860

Humans have great difficulty to internalize and to be sure of what they hear or are told - and in turn to adjust their actions - once having experienced something though by themselves, they stick stubbornly with the cerntainty of that personal, individual and often only exemplary experience - and I'm no exception from that. Absolute doubtlessness - absolute certainty - gained by very own experience made in far or near past under then circumstances make oneself a prisoner of that past and blind to accept present and future options and no-options / constraints - not noticing that circumstances most likely have changed. Blind spot is another term for that.

With a fresh look at the implementation / internals / performance, I will elaborate on code variations empirically in the beginning, and over time more theoretically - in an a priori way - the more I (really) understand.

Usage of a very high-level language let's one quickly make things happen and equally quickly forget what is really going on under the hood. Back to the roots is as bloody-red as the red beets themselves... but it is fun.

Regarding temporary memory usage, I was thinking of using the require() and then the un-require() - of which I read about in some posts or tutorials, but can not recall top of my head the actual function call.... will come back and edit the post.

[espruino-discuss]

Posted at 2014-10-02 by @allObjects

@cephdon - you are absolutely right - when there is no time constraint using the practical unlimited space of the SD card is a way out. For the first of my three blocks of data this is a valid approach. For the second and third one, access and process performance are crucial. Therefore they have to live in the memory. If all options fail - space and time - I may resort to inline assembler creating the values from a very compressed, byte based/bit banged memory chunk, and pass them back to the JavaScript context.

[espruino-discuss]

Posted at 2014-10-02 by DrAzzy

In-between SD card and RAM, you could use something like an AT24-series eeprom for additional storage?

[gfwilliams]

Posted at 2014-10-02 by @gfwilliams

There's also the ability to store the data in Flash memory. If your board is one of the ones that actually has 384kB (I think all of them do!) you've got at least 100kB at the end to fiddle with, and you can use peek to get at the data.

@cephdon - just to say you can still open the file and skip() forwards. I have now added seek though, so it'll be in 1v71 or the Git builds.

[espruino-discuss]

Posted at 2014-10-02 by DrAzzy

Bigram builds tell it the chip has 512k, and they seem to work...

[gfwilliams]

Posted at 2014-10-02 by @gfwilliams

Wow, ok - so yeah - lots of data.

I'd be tempted to keep telling the bigram builds they only have 256k though. That's solve this problem you're having with upgrades breaking process.memory() - it'll also leave the entire upper 256kb free for use for whatever you wanted.

[espruino-discuss]

Posted at 2014-10-02 by DrAzzy

But then it wouldn't have room to save() the 64k of program code, would it?

[espruino-discuss]

Posted at 2014-10-03 by cephdon

@gordon nice!
I wasn't actually attempting to push for that feature, just noting what we could do with it. However, since we will have it, is it based on relative or absolute positions?

[gfwilliams]

Posted at 2014-10-03 by @gfwilliams

@drazzy, good point :) By turning on '-Os' you could still get it all in if you wanted though.

It's just that with the current setup, the memory you can use is somewhere between addresses 220kB and 430kB - not as easy as just saying 'anything past 256 and you're fine'.

@cephdon it's absolute positions. 'skip' can skip forwards for relative positions, or you can always keep track of the file positions yourself.

[espruino-discuss]

Posted at 2014-10-04 by cephdon

@gordon,
Thank you.
No worries. Each entry could have it's absolute position and then the sizes of the previous and current lines before the key and data. Just a little math to get to the absolute position for the beginning of each one.

So it could still be done. Awesome.