Please don't put too much time or effort into an answer, just looking for ideas.
I'm trying to do something I get the sense a lot of people want to do, I want to be able to use a system, probably an array, where you can place true booleans and remove false ones on the fly, so when the array/list is scanned, no time is wasted on empty values.
Right now, I have an array of 88 members, and I'm looping through that array hundreds of times per function run, it's a huge, very inefficient bottleneck. But solutions I've found regarding dynamic arrays involve using containers, vectors and other programming concepts that are currently beyond my abilities. Any other method I can think of introduces the same looping issue in different forms.
Give up the idea of using dynamic arrays in the small memory footprint of a microcontroller. Have you considered using the bits of a few bytes instead of boolean variables to speed things up ?
The Arduino will loop through 88 array entries in no time at all so I suspect that something else in the code that you have not posted is causing a problem
To get any more help you will need to post your code and give more details of the project and the problems that you are having. As a wild guess you are using delay() in the sketch and/or blocking while loops and possibly variables of inappropriate types but without your code we cannot know
In particular note the advice to Auto format code in the IDE and to use code tags when posting code here as it prevents some combinations of characters in code being interpreted as HTML commands such as italics, bold or a smiley character, all of which render the code useless
If the code exceeds the 9000 character inline limit then attach it to a post
It sounds like you want to dynamically insert and delete members. The most efficient method is a linked list. You can Google that. You can use the C++ list container class or implement your own. Indeed you can probably just download an implementation. If you really do need the efficiency then you will have to take the time to understand it.
However, with limited memory you should be careful.
+1 on a look at your code and a description of what you are trying to accomplish.
There are plenty of years-old data structures that should make this very faster. Many are suitable even for dinky little projects on dinky little Arduinos. Some are ideal.
Sooner later you will want to bring some mildly advanced concepts into your abilities.
UKHeliBob:
Give up the idea of using dynamic arrays in the small memory footprint of a microcontroller. Have you considered using the bits of a few bytes instead of boolean variables to speed things up ?
The Arduino will loop through 88 array entries in no time at all so I suspect that something else in the code that you have not posted is causing a problem
To get any more help you will need to post your code and give more details of the project and the problems that you are having. As a wild guess you are using delay() in the sketch and/or blocking while loops and possibly variables of inappropriate types but without your code we cannot know
In particular note the advice to Auto format code in the IDE and to use code tags when posting code here as it prevents some combinations of characters in code being interpreted as HTML commands such as italics, bold or a smiley character, all of which render the code useless
If the code exceeds the 9000 character inline limit then attach it to a post
UKHeliBob:
Give up the idea of using dynamic arrays in the small memory footprint of a microcontroller. Have you considered using the bits of a few bytes instead of boolean variables to speed things up ?
The Arduino will loop through 88 array entries in no time at all so I suspect that something else in the code that you have not posted is causing a problem
To get any more help you will need to post your code and give more details of the project and the problems that you are having. As a wild guess you are using delay() in the sketch and/or blocking while loops and possibly variables of inappropriate types but without your code we cannot know
In particular note the advice to Auto format code in the IDE and to use code tags when posting code here as it prevents some combinations of characters in code being interpreted as HTML commands such as italics, bold or a smiley character, all of which render the code useless
If the code exceeds the 9000 character inline limit then attach it to a post
There's no problem with my code, I'm just trying to make it faster and more efficient. I'm only asking about methods of managing dynamic variables/lists.
alto777:
+1 on a look at your code and a description of what you are trying to accomplish.
There are plenty of years-old data structures that should make this very faster. Many are suitable even for dinky little projects on dinky little Arduinos. Some are ideal.
Sooner later you will want to bring some mildly advanced concepts into your abilities.
a7
I feel like every time I post on this forum, everyone demands unrelated and unnecessary information. Everything I'm asking about is contained in my question. There is no example that will make it clearer, and no explanation of use case that will change it. I'm just asking about general alternatives to looping through big arrays hundreds and hundreds of times.
If you've got a known maximum number of widgets that you have to maintain an active list of, then from a memory allocation point-of-view, it's relatively safe and quick to have two lists, an active list and a free list.
But without knowing a little more, it's all just hand-waving.
Dr-Zee:
I feel like every time I post on this forum, everyone demands unrelated and unnecessary information. Everything I'm asking about is contained in my question.
No one "demands" anything, but the better the quality of information you provide, then better and more targeted answers will likely result.
ToddL1962:
It sounds like you want to dynamically insert and delete members. The most efficient method is a linked list. You can Google that. You can use the C++ list container class or implement your own. Indeed you can probably just download an implementation. If you really do need the efficiency then you will have to take the time to understand it.
However, with limited memory you should be careful.
I was not aware of linked lists. Thank you very much. I'll check them out.
TheMemberFormerlyKnownAsAWOL:
No one "demands" anything, but the better the quality of information you provide, then better and more targeted answers will likely result.
Your call. Always.
I understand, It's just frustrating that the people who take the time Answer lots and lots of questions tend to always assume that the question you're asking is not the question you're asking, it must be something else.
This isn't to say I don't appreciate everyone's time and attention which I very much do.
jimLee:
Linked list : You can play with them today! Well, at least one example of them. Grab LC_baseTools from your library manager and look at lists.h
TheMemberFormerlyKnownAsAWOL:
If you've got a known maximum number of widgets that you have to maintain an active list of, then from a memory allocation point-of-view, it's relatively safe and quick to have two lists, an active list and a free list.
But without knowing a little more, it's all just hand-waving.
There can be any number of flipped booleans between 0 and 88.
The use case is a non-blocking LED fade function. This is bottlenecking because of the speed of updates that's required to run a linear fade without dropping frames + the overhead of doing lots of 32bit color conversions. I'm running it using multithreading on an ESP32 so the system is very powerful, I'm just working to get my overhead as low as I possibly can, everywhere I can. When things are quiet time through the loop is around 16ms, but as more fades begin activating it drops to in the range of 50-200ms. for every single fade step value on every single led, it's running through this 88 value loop. I think I can do better.
I'll try this out. Thanks, former AWOL
You do realize, using a linked list, beyond a certain number of elements it will certainly be considerable slower to parse the list than the original array. With only a few elements in the array it will likely be faster, but I suspect by the time the list is perhaps 1/4 filled, it will be slower, and when full it will be MUCH slower than it is now. And each time you add or remove or move elements in the list it will be MUCH slower, since you'll have to go through malloc, which has to walk the free memory list. If you want fast, dynamic allocation is NOT the way to go.
Most likely, the correct/best answer to your problem was given above - pack eight values into a byte, or 32 into an unsigned int since you're on an ESP. You can then test for all true, or all false or any other desired pattern in each byte or int with a single compare operation.
But, again, since you don't allow us to know what you're really DOING with the data, nobody here can really say what the best answer is with any certainty. We can only guess based on the limited information you've provided.
This seems like an XY problem. Looping through 88 elements is fast (as UKHeliBob mentioned in #1). Say it takes 5 clock cycles to iterate over each element to decide whether to do something with it; at 16 MHz, that's only 27.5 microseconds!
Changing to a dynamic list of some sort is likely to make it slower as the code may have to traverse list pointers and such (which is slower than simply indexing into a fixed array).
We can let the OP have his fun. We can watch him waste his time.
The disadvantage of not fully specifying the problem is that, I dunno, a dozen or so people won’t be competing all over each over to come up with the crispest most memory efficient quickest way to do this.
The easiest method by far for explaining why you want to do what you talking about is to show us the problem in context. If you are reticent about sharing your super secret or crummy code, write a tiny program that demonstrates everything you need the solution to afford in the context of something that we could play with ourselves.
Since I get more mileage out of (re)inventing my own data structures and algorithms I usually don’t start with a library I download, coming to grips with which might easily a) burn through a bunch of time only to b) turn out to be inappropriate.
In this case knowing only what we do linked lists don’t seem to be the right knife for this butter.
Plus I can say I damn curious about how this particular problem figures into any project. It may seem rude to make “demands” but it is sort of the contract you make here. You ask, we answer, and the dialog is for the benefit of not just you and your stupid project, not just for us\su\ the competitive show-off types, but for all who may only be lurking, not even registered, users, who scrape up a bit more knowledge with each fully posed question and the variety of answers.
I know I always learn about something here, usually things that have been invented and become possible and affordable while I had my head down. Occasionally a programming concept too. Or language arcana.
Sadly it looks like there’s no alternative to starting to work on my taxes. Yes, automated software helps, but it’s still a slog I procrastinate over, supposed to be done by March 1, a perennial elusive goal.
I figured if he wanted to learn about alternative data structures then why not; however, it is correct to say that with a small number of entries it really isn't worth it. Even with a large number of entries you would have to do a lot of insertions and deletions in order to find benefit.