Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Allow typed arrays over 64KB #2036

Closed
fanoush opened this issue Aug 13, 2021 · 25 comments
Closed

Allow typed arrays over 64KB #2036

fanoush opened this issue Aug 13, 2021 · 25 comments

Comments

@fanoush
Copy link
Contributor

fanoush commented Aug 13, 2021

as per http://forum.espruino.com/conversations/366505/#16122927

Array index for typed arrays is now 16 bit so one cannot make arrays over 64k

>a=new Uint8Array(65536)
Uncaught Error: Invalid length for ArrayBuffer
...
>a=new Uint16Array(32768)
Uncaught Error: Invalid length for ArrayBuffer
...
>Graphics.createArrayBuffer(240,240,16)
Uncaught Error: Invalid length for ArrayBuffer

Couple of targets now have SRAM >=128KB so bigger arrays can be practical for data or framebuffer
It would be nice to add at least a bit or two so arrays up to 128/256KB are possible. LINUX target could use even more.

@gfwilliams
Copy link
Member

I had a play with this yesterday and it wasn't as easy as hoped. You could get the extra bits into the enum, but then a few bits of code have to have the direct reference to array size changed in them.

@fanoush
Copy link
Contributor Author

fanoush commented Aug 13, 2021

BTW just tried strings over 64K in LINUX build and looks like E.toArrayBuffer() wraps length to 16 bits, not sure if it is bug or feature

>s="".padEnd(65536)
="                 " ... "                 "
>s=s.padEnd(65540,'a')
="                 " ... "             aaaa"
>a=E.toArrayBuffer(s)
=new Uint8Array([32, 32, 32, 32]).buffer
>s.length
=65540
>a.length
=4

@fanoush
Copy link
Contributor Author

fanoush commented Jan 13, 2023

Another case of this limitation https://forum.espruino.com/comments/16824971/
so it is not only about RAM but also about bigger storage files - Storage.readArrayBuffer breaks when file is over 64KB.
There are workarounds by iterating over <64K substrings returned from Storage.read but still it can be seen that we are hitting limits with this.

@gfwilliams
Copy link
Member

I know... I did attempt to get a fix in for this, but it didn't appear to be working...

The idea was to increase the length to 24 where we thought we had enough memory for it:

diff --git a/src/jsvar.c b/src/jsvar.c
index aac08bdcb..cc9c8eff0 100644
--- a/src/jsvar.c
+++ b/src/jsvar.c
@@ -1126,6 +1126,8 @@ JsVar *jsvNewNativeString(char *ptr, size_t len) {
   if (len>JSV_NATIVE_STR_MAX_LENGTH) len=JSV_NATIVE_STR_MAX_LENGTH; // crop string to what we can store in nativeStr.len
   JsVar *str = jsvNewWithFlags(JSV_NATIVE_STRING);
   if (!str) return 0;
+  if (len > JSV_NATIVE_STR_MAX_LENGTH)
+    len = JSV_NATIVE_STR_MAX_LENGTH;
   str->varData.nativeStr.ptr = ptr;
   str->varData.nativeStr.len = (JsVarDataNativeStrLength)len;
   return str;
@@ -1150,7 +1152,7 @@ JsVar *jsvNewArrayBufferFromString(JsVar *str, unsigned int lengthOrZero) {
   arr->varData.arraybuffer.type = ARRAYBUFFERVIEW_ARRAYBUFFER;
   assert(arr->varData.arraybuffer.byteOffset == 0);
   if (lengthOrZero==0) lengthOrZero = (unsigned int)jsvGetStringLength(str);
-  arr->varData.arraybuffer.length = (unsigned short)lengthOrZero;
+  arr->varData.arraybuffer.length = (JsVarArrayBufferLength)lengthOrZero;
   return arr;
 }
 
diff --git a/src/jsvar.h b/src/jsvar.h
index 54b076b64..e7517aab0 100644
--- a/src/jsvar.h
+++ b/src/jsvar.h
@@ -118,18 +118,30 @@ typedef enum {
   ARRAYBUFFERVIEW_INT32   = 4 | ARRAYBUFFERVIEW_SIGNED,
   ARRAYBUFFERVIEW_FLOAT32 = 4 | ARRAYBUFFERVIEW_FLOAT,
   ARRAYBUFFERVIEW_FLOAT64 = 8 | ARRAYBUFFERVIEW_FLOAT,
-} PACKED_FLAGS JsVarDataArrayBufferViewType;
+} PACKED_FLAGS JsVarDataArrayBufferViewType; // 16 bits
 #define JSV_ARRAYBUFFER_GET_SIZE(T) (size_t)((T)&ARRAYBUFFERVIEW_MASK_SIZE)
 #define JSV_ARRAYBUFFER_IS_SIGNED(T) (((T)&ARRAYBUFFERVIEW_SIGNED)!=0)
 #define JSV_ARRAYBUFFER_IS_FLOAT(T) (((T)&ARRAYBUFFERVIEW_FLOAT)!=0)
 #define JSV_ARRAYBUFFER_IS_CLAMPED(T) (((T)&ARRAYBUFFERVIEW_CLAMPED)!=0)
 
+#if JSVAR_DATA_STRING_LEN<8
+typedef uint16_t JsVarDataNativeStrLength;
+#define JSV_NATIVE_STR_MAX_LENGTH 65535
+typedef uint16_t JsVarArrayBufferLength;
 #define JSV_ARRAYBUFFER_MAX_LENGTH 65535
+#define JSV_ARRAYBUFFER_LENGTH_BITS
+#else
+typedef uint32_t JsVarDataNativeStrLength;
+#define JSV_NATIVE_STR_MAX_LENGTH 0xFFFFFFFF
+typedef uint32_t JsVarArrayBufferLength;
+#define JSV_ARRAYBUFFER_MAX_LENGTH 0xFFFFFF
+#define JSV_ARRAYBUFFER_LENGTH_BITS : 24
+#endif
 
 /// Data for ArrayBuffers. Max size here is 6 bytes in most cases (4 byte data + 2x JsVarRef)
 typedef struct {
   unsigned short byteOffset;
-  unsigned short length;
+  JsVarArrayBufferLength length JSV_ARRAYBUFFER_LENGTH_BITS;
   JsVarDataArrayBufferViewType type;
 } PACKED_FLAGS JsVarDataArrayBufferView;
 
@@ -139,14 +151,6 @@ typedef struct {
   uint16_t argTypes; ///< Actually a list of JsnArgumentType
 } PACKED_FLAGS JsVarDataNative;
 
-#if JSVARREF_SIZE==1
-typedef uint16_t JsVarDataNativeStrLength;
-#define JSV_NATIVE_STR_MAX_LENGTH 65535
-#else
-typedef uint32_t JsVarDataNativeStrLength;
-#define JSV_NATIVE_STR_MAX_LENGTH 0xFFFFFFFF
-#endif
-
 /// Data for native strings
 typedef struct {
   char *ptr;

IMO that'd be preferable to the other option (of trying to poke the top bits into the ArrayBuffer enum)

@fanoush
Copy link
Contributor Author

fanoush commented Jan 13, 2023

Thanks for the patch. Tried in on linux build (which also has this limit even in 64bit) and it helps partially. THe example from above is better.

>a=new Uint8Array(65536)
Uncaught Error: Invalid length for ArrayBuffer

 at line 1 col 23
a=new Uint8Array(65536)
                      ^
>s="".padEnd(65536)
="                 " ... "                 "
>s=s.padEnd(65540,'a')
="                 " ... "             aaaa"
>a=E.toArrayBuffer(s)
=new Uint8Array([32, 32, 32, 32, 32,  ... 32, 97, 97, 97, 97]).buffer
>a.length
=65540
>

E.toArrayBuffer() works better now. Uint8Array constructor still has this 16bit check.

@fanoush
Copy link
Contributor Author

fanoush commented Jan 13, 2023

so when removing extra check from here

if (byteLength < 0 || byteLength>65535) {

it got better for arraybuffer but still wrong for arrays

>a=new Uint8Array(65536)
=new Uint8Array(0)
>a[65535]
=undefined
>a.buffer
=new ArrayBuffer(65536)
>a.buffer[65535]
=0
>a.buffer[65535]=255
=255
>a
=new Uint8Array(0)
>a.buffer
=new Uint8Array([0, 0, 0, 0, 0,  ... 0, 0, 0, 0, 255]).buffer
>

@fanoush
Copy link
Contributor Author

fanoush commented Jan 13, 2023

will test on nrf52 later but anyway even if it worked just for ArrayBuffer type it would be improvement as this works now

>g=Graphics.createArrayBuffer(240,240,16)
=Graphics: {
  buffer: new ArrayBuffer(115200)
 }
>

@fanoush
Copy link
Contributor Author

fanoush commented Jan 13, 2023

also this works

>a=new Uint16Array(65535)
=new Uint16Array(65535)
>a.buffer
=new ArrayBuffer(131070)
>a[65534]=32000
=32000
>a
=new Uint16Array([0, 0, 0, 0, 0,  ... 0, 0, 0, 0, 32000])
>

so you can't have index array over 16 bits but the underlying buffer seems to work over 64K with 16bit type

@fanoush
Copy link
Contributor Author

fanoush commented Jan 13, 2023

Maybe I got it, this line

typedArr->varData.arraybuffer.length = (unsigned short)length;

>a=new Uint16Array(65536)
=new Uint16Array(65536)
>a[65535]=32000
=32000
>a
=new Uint16Array([0, 0, 0, 0, 0,  ... 0, 0, 0, 0, 32000])
>a=new Uint8Array(65536*2)
=new Uint8Array(131072)
>a
=new Uint8Array(131072)
>a[131071]=128
=128
>a
=new Uint8Array([0, 0, 0, 0, 0,  ... 0, 0, 0, 0, 128])
>

@gfwilliams
Copy link
Member

Ahh, great! maybe you could run a build with that for a while? I think I was a bit concerned that it might have meant that some references got overwritten, so when it gets freed things could potentially get unstable

@fanoush
Copy link
Contributor Author

fanoush commented Jan 13, 2023

OK, I will. So far this was from linux build but I needed this for framebuffer on 52840 watches like 240x320 in 256 colors or even 12bit. Also the G5 watch https://forum.espruino.com/conversations/373361/ which even in 4 bits is over 64K.

So I will test this however in this use case I will never free the buffer. Do you suppose this may happen when just smaller stuff around it gets freed and allocated over time? Otherwise maybe some random size allocation/free test that runs continuously would be better.

@gfwilliams
Copy link
Member

Well, testing like that is still definitely better than nothing - if it can survive an E.defrag and garbage collect then there's a good chance it's ok.

I had actually made the change for a high res LCD too, but it didn't seem stable for me (but I can't remember why now though!)

@fanoush
Copy link
Contributor Author

fanoush commented Jan 13, 2023

In the linux build (without RELEASE=1) I am running this for quite some time

function randAlloc(){var r=Math.random()*2*65535|0;var a=new Uint8Array(r);for(var i=0;i<r;i+=10)a[i]=i;return a;}
var a,b;
setInterval(()=>{a=randAlloc();},3000);
setInterval(()=>{b=randAlloc();},5000);
setInterval(()=>{var x=5;E.defrag();},4000);

and so far the console works, no error messages/crashes, looks good so far

EDIT: also added

setInterval(()=>{print(process.memory());},5500);
function check(arr){var r=arr.length;for(var i=0;i<r;i+=10) if(arr[i]!=i%256) print("error ",i);}
setInterval(()=>{Math.round(Math.random())?check(a):check(b);},3600);

just to see some output and everything is still good.
Anyway, will test further in nrf52840 watches.

@fanoush
Copy link
Contributor Author

fanoush commented Jan 15, 2023

tested a bit over weekend but testing is a bit tricky, the stuff above is too slow and gives out of memory and freezes quickly.
I have tested this on NRF52840 dongle with 14000 variables and reduced the test to this

var ratio=1.5;
function randAlloc(){var r=Math.random()*ratio*65535|0;ratio=1/ratio;var t=getTime();var a=Uint8Array(r);print(r,"took",(getTime()-t)*1E3,"ms"); t=getTime();for(var i=0;i<r;i+=100)a[i]=i%256;print(r,"iteration step",(getTime()-t)*1E5/r,"ms, addr",E.getAddressOf(a,true).toString(16)); return a;}
var a,b;
setInterval(()=>{a=Uint8Array(1);a=randAlloc();},6000);
setInterval(()=>{b=Uint8Array(1);b=randAlloc();},5000);

example output attached

Overall it works, I saw no corruption but lot of out of memory situations (see end of the log), with shorter intervals even freeze (as the code inside took longer than next interval came?).
However big arrays slow stuff down, creating bigger array can take over 100ms and looks like even using it is slow. I have added native address to see if it is flat array and it can be seen that when addr is 0 everything is slow - both allocation and iteration.

It was surprising that allocation of the array always depends on the size (even for case with flat array = one block).

Also what is strange is that tab completion on the array properties also depend on size. var a=new Uint8Array(10), then typing a.le+tab fills 'length' immediately but when the array is larger it take more and more time, for 60000 array it is significant. It is same even right after reset() with just that one array in memory. Not sure if it is a symptom of something suboptimal that may affect normal execution.

log.txt

@gfwilliams
Copy link
Member

Interesting, thanks!

What could be happening with the test is that the memory is getting fragmented and then it's not able to allocate a flat area of memory for the array - so instead it allocates it as a normal string, which would be slow to access, as you need to iterate to the correct point inside them. E.getAddressOf(v, true)!=0 would tell you that

Allocation will be slow too since it's having to iterate to find a free area - but the idea is that especially for big arrays you allocate once and then re-use it.

Also what is strange is that tab completion on the array properties also depend on size

That is interesting! I guess it's not surprising in retrospect - we have a function that iterates over all fields inside an object (jswrap_object_keys_or_property_names_cb) that is used for Object.keys/for..in/etc. Tab complete just uses that so I guess it checks every array element!

I've stuck a fix in for that now.

Where are your changes to enable this? Is it literally just what I posted plus the two changes you mentioned above?

@fanoush
Copy link
Contributor Author

fanoush commented Jan 16, 2023

Where are your changes to enable this? Is it literally just what I posted plus the two changes you mentioned above?

Yes. In both cases I just removed it

diff --git a/src/jswrap_arraybuffer.c b/src/jswrap_arraybuffer.c
index a0bda2978..9baf16442 100644
--- a/src/jswrap_arraybuffer.c
+++ b/src/jswrap_arraybuffer.c
@@ -237,7 +237,7 @@ Arrays of this type include all the methods from
 Create an Array Buffer object
  */
 JsVar *jswrap_arraybuffer_constructor(JsVarInt byteLength) {
-  if (byteLength < 0 || byteLength>65535) {
+  if (byteLength < 0) {
     jsExceptionHere(JSET_ERROR, "Invalid length for ArrayBuffer\n");
     return 0;
   }
@@ -542,7 +542,7 @@ JsVar *jswrap_typedarray_constructor(JsVarDataArrayBufferViewType type, JsVar *a
   if (typedArr) {
     typedArr->varData.arraybuffer.type = type;
     typedArr->varData.arraybuffer.byteOffset = (unsigned short)byteOffset;
-    typedArr->varData.arraybuffer.length = (unsigned short)length;
+    typedArr->varData.arraybuffer.length = /*(unsigned short)*/length;
     jsvSetFirstChild(typedArr, jsvGetRef(jsvRef(arrayBuffer)));

     if (copyData) {

the || byteLength>65535 seemed redundant as it is checked few lines below again and forcing the type - should be replaced by new type you made? this part might be the missing bit as truncated length could cause some corruption issues later?

Allocation will be slow too since it's having to iterate to find a free area - but the idea is that especially for big arrays you allocate once and then re-use it.

Yes, indeed, I just grab one big buffer at the beginning. It makes sense that in case of fragmented space it takes time to fit the fragmented string into holes, however if just allocating one piece why it takes longer to grab it. Maybe clearing to zero take 21ms here?

>var t=getTime();var a=new Uint8Array(150000);(getTime()-t)*1e3
=21.94213867187

BTW this doesn't look OK, shouldn't delete a free it? The out of memory case probably leaves something in bad state?
log.txt
It is probably unrelated to arrays over 64KB, just easier to reproduce now(?)

@gfwilliams
Copy link
Member

Ok, great - I think it's good to error if an arraybuffer is too big, and now we have a define for the max size so I'll just tweak that.

I just grab one big buffer at the beginning.

Maybe it's worth statically allocating it, and then using E.memoryArea to create a 'native string' that just references it. That would be a lot faster I bet, and in a lot of ways makes things easier.

if just allocating one piece why it takes longer to grab it

Because it still has to check every JsVar in the line is empty before allocating, and then as you say it must clear it. I think that's probably it.

BTW this doesn't look OK, shouldn't delete a free it?

Yes, it should do - that looks very strange...

@gfwilliams
Copy link
Member

Ok, just merged in 35e8f24

@fanoush
Copy link
Contributor Author

fanoush commented Jan 18, 2023

Great, I just synced with your changes and it still works. However even with recent fix you did, the delete a still does not free it, behaves same as before. But I guess it was fix for that out of memory situation I had since when running that same allocation test I no longer get out of memory after a while. Maybe I even have less zeroes for flat buffer native address.

Maybe it's worth statically allocating it, and then using E.memoryArea to create a 'native string' that just references it.

Like hardcoding in the firmware build and reducing variables? I wanted flexibility of selecting bit depth at boot time to have more colors or more free memory.

@fanoush
Copy link
Contributor Author

fanoush commented Jan 18, 2023

oh, sorry, no, just after I wrote it I got it again :-(

69073 took 13.0615234375 ms
69073 iteration step 0.42657364932 ms, addr 20021f48
42996 took 63.26293945312 ms
42996 iteration step 5.33049733641 ms, addr 0
ERROR: Ctrl-C while processing interval - removing it.
Execution Interrupted during event processing.
New interpreter error: CALLBACK,LOW_MEMORY,MEMORY
600 took 28.86962890625 ms
600 iteration step 0.53405761718 ms, addr 20004000

@gfwilliams
Copy link
Member

Like hardcoding in the firmware build and reducing variables? I wanted flexibility of selecting bit depth at boot time to have more colors or more free memory.

Ahh, ok. But yes, hard-coding it would make life easier probably.

The delete a thing is tricky. Does it happen with smaller arraybuffers? Or only after the MEMORY error?

I think you will still get the MEMORY area for the reasons I mentioned before (fragmentation) if you keep allocating alternately though. You could try running E.defrag() just before you allocate each array, but right now we don't defrag flat strings so it may be of limited use

@fanoush
Copy link
Contributor Author

fanoush commented Jan 18, 2023

The delete a thing is tricky. Does it happen with smaller arraybuffers? Or only after the MEMORY error?

only after memory error. I have replicated it also with clean older build before arrays over 64KB were added in LINUX build.
I changed board file to set variable count from 0 to 14000 so it works in similar way and tried this, can be seen first delete works and after out of memory is hit it no longer frees it. I am assigning to same c variable as I guess it is the old value that gets lost before it is 'assigned' the failed allocation.

____                 _
|  __|___ ___ ___ _ _|_|___ ___
|  __|_ -| . |  _| | | |   | . |
|____|___|  _|_| |___|_|_|_|___|
         |_| espruino.com
 2v16.114 (c) 2021 G.Williams

Espruino is Open Source. Our work is supported
only by sales of official boards and donations:
http://espruino.com/Donate

>var a=new Uint8Array(65000)
=new Uint8Array(65000)
>var b=new Uint8Array(65000)
=new Uint8Array(65000)
>process.memory()
={ free: 6736, usage: 7264, total: 14000, history: 7,
  gc: 0, gctime: 0.611, blocksize: 18 }
>var c=new Uint8Array(65000)
=new Uint8Array(65000)
>process.memory()
={ free: 3120, usage: 10880, total: 14000, history: 13,
  gc: 0, gctime: 0.277, blocksize: 18 }
>delete c
=true
>process.memory()
={ free: 6736, usage: 7264, total: 14000, history: 15,
  gc: 0, gctime: 0.207, blocksize: 18 }
>var c=new Uint8Array(65000)
=new Uint8Array(65000)
>process.memory()
={ free: 3120, usage: 10880, total: 14000, history: 15,
  gc: 0, gctime: 0.291, blocksize: 18 }
>var c=new Uint8Array(65000)
Execution Interrupted
New interpreter error: LOW_MEMORY,MEMORY
>process.memory()
={ free: 3120, usage: 10880, total: 14000, history: 4,
  gc: 0, gctime: 0.29, blocksize: 18 }
>delete c
=true
>process.memory()
={ free: 3120, usage: 10880, total: 14000, history: 9,
  gc: 0, gctime: 0.101, blocksize: 18 }
>

@gfwilliams
Copy link
Member

Thanks! Just fixed this with 90d13c1 - I'd been imagining it was = but it's actually to do with how var handled errors/out of memory

@gfwilliams
Copy link
Member

So... do we think this one is actually closed now? I think we're probably good...

@fanoush
Copy link
Contributor Author

fanoush commented Jan 19, 2023

Yes it is the var indeed, I just used command history before so var was always there. This does not trigger it and older value stays there after failure.

>var a=new Uint8Array(130000)
=new Uint8Array(130000)
>a=new Uint8Array(130000)
Execution Interrupted
New interpreter error: LOW_MEMORY,MEMORY
>process.memory()
={ free: 6741, usage: 7259, total: 14000, history: 4,
  gc: 0, gctime: 0.177, blocksize: 18 }
>a
=new Uint8Array(130000)
>delete a
=true
>process.memory()
={ free: 13968, usage: 32, total: 14000, history: 11,
  gc: 0, gctime: 0.422, blocksize: 18 }
>

this is still without the fix, after updating to your fix both var and without var works fine

@fanoush fanoush closed this as completed Jan 19, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants