The Lounge - CodeProject

If you cross Santa, you get elephant all from him!

"If we don't change direction, we'll end up where we're going"

OriginalGriff wrote:
If you cross Santa

They didn’t cross Santa. They crossed Jesus! (But that’s more about Easter)

If you can't laugh at yourself - ask me and I will do it for you.

I needed a way to compare an escaped string coming out of a file with a series of unescaped strings passed to a function to see if one of them matches.

The easy way:
Load the string from the file, unescape it and compare each string in turn.
Pro: easy to code and maintain
Con: Requires the entire string to live in memory, requiring a buffer for it first.

The hard way:
Load the string one character at a time from a file, while deescaping inline, keep a list of pointers to the current location for each string you're checking against, compare and advance each of the string pointers in turn. If one doesn't match, disqualify it by setting its pointer to null, and when you're done see if you wound up with an undisqualified string.
Pro: only needs a character at a time in memory, plus scratch for the pointers
Con: Weird to write and maintain.

Because I'm coding on extremely low memory scenarios, i picked the hard way. I hate this code though, but there is an irresponsible part of me that enjoyed writing it. $Shucks | :-\$

Real programmers use butterflies

Is it a fixed or dynamic list of strings to check.
If it is fixed, us your lex/parser-fu and create a DFA/lexer to check for the strings.
DFAs are very memory efficient, as you know.

"Time flies like an arrow. Fruit flies like a banana."

The strings are determined at runtime so building a DFA is not desirable.

Edit: It might be possible to pre-bake DFAs for predefined queries but that would be more of a code generation thing. The thing is I don't have the RAM for DFA tables so I'd need it to be compiled.

Real programmers use butterflies

How about creating a tree from the list of strings characters. Then you could attempt to traverse the tree as the characters come in and if you get to a leaf, you have a match. If you would need to buffer a bit so you can backtrack, but I think you know how to do this.

"Time flies like an arrow. Fruit flies like a banana."

The biggest concern is RAM. Speed is secondary. I need to use as few bytes as possible for this. The strings are already allocated because 99% of the time the passed in strings are constant so i don't waste bytes reallocating them in a different form. I suppose I could turn the list of strings i'm using into a tree but there are fewer than 5 strings for the average query. Usually one or two, maybe three. Smile | :)

Real programmers use butterflies

I have a slight suspicion that this 'minimal RAM' has become an obsession with you. I have been working with embedded processors for 10+ year, and seen how available resources have grown for off-the-shelf embedded chips. 10+ years ago, IoT was not a concept, but those chips (or rather: their successors) I worked with ten years ago are those used in IoT things today. Today they are capable, low power, modern.

If you look upon yourself as a masochist, you may of course go for something like a 2903 four-bit bit slice processor (really intended for combining 4 or 8 to a 16- or 32-bit CPU), where you have to write the microcode yourself. If you are not quite as much a die-hard masochist, you may go for an 8-bit CPU with 16 bits memory bus, but only 4096 bytes allocated to RAM.

That is for masochists only. Not The Way to solve a problem, create a solution. If you really need to implement an IoT solution, there are numerous processor alternatives giving you access to lots of resources way beyond what your are talking about.

Your attitude reminds me of the very first international conference I ever visited, on free text search, where one paper showed how they had succeeded in reducing the space requirement for index terms by (slightly less than) one bit per index term. Maybe the technology was great that year, but I have never heard of them later.

For being blunt: Anno 2020, no solution will earn everlasting accolade because it fit in 4K RAM. Not even 16K RAM. If you move up to 64K (or more), that is what everybody is doing. Nothing special about that.

'I managed to fit it into 4K!' is a battle arena left long ago. Sure: Some groups have developed it into an extreme art - you will find a huge collection at pouët.net[^]. One of my favorites is Skyline[^] - do download it to see what they managed to squeeze into 4096 bytes - it it totally unbelievable!

But that is not 'problem solving', not 'usable' in any way. It is just show off: Ain't I clever? Yes, you are, and impressively so.

Now, let us go back to productive world. Let us solve real world problems of today, using tools of today.

I am targeting 32-bit arduinos. Eventually I will target the 8 bit ones - most of my code is 8 bit ready but i'm saving actually targeting them for now. Regardless, i wanted to get the ram use realistic for those devices

They have varying amounts of ram. The Atmega2560 has 8kB. some others have 32kb. My current monster is 32 bit and has 520kb but that's an exception, not the rule, and it has multiple cores so i'm not the only thread using ram anyway.

I do enjoy the challenge, but it's not for nothing.

Edit: Also, so far I have only been doing very simple queries out of large documents. The less memory they take per, the more complex queries I can compose with them.

Atmegas still sell. ArduinoJson is still used all the time. I have to disagree with you.

Real programmers use butterflies

modified 18-Dec-20 20:32pm.

honey the codewitch wrote:
I will target the 8 bit ones - most of my code is 8 bit ready but i'm saving actually targeting them for now

OK, go ahead, but I have a feeling that you are spending resources on designing improved horseshoes.

I would disagree, as I suspect the author of the popular ArduinoJson library would as well.

Real programmers use butterflies

honey the codewitch wrote:
this is one of the weirdest things i've written in a long time

Definitely not Poke tongue | ;-P

Do not escape reality : improve reality !

I'm with you. Strings are always compared one character at a time anyway. Write a custom string comparer.

I've only glanced at the article, but CP's Daily News this morning pointed out that Google had purchased a company that "turns your old Windows 7 PC into a Chrome OS machine".

How old are we talking about? Chrome, the browser, is a pig, no matter what the underlying OS might be. The most resource-hungry thing you can ask an old box to do is to run a web browser--even the simplest pages nowadays download a few MBs worth of crap, and the scripting built into them to manipulate the content on the fly makes the poorly-performing apps of yesteryear look snappy in comparison.

The moment Edge switched to being Chrome-based, it became as much of a hog. I'm not blaming MS for that - something about pigs and lipstick.

I'm all about repurposing old systems and giving them new life. I'm getting to like Linux a lot for that. But where things start to fall apart is when you load a resource-hungry browser. I've witnessed this first-hand more times than I care to count: A clean Windows 7 system with IE performs better than a lean Linux distribution with Chrome. Of course, IE is no longer a contender, but we're quickly running out of viable alternatives.

Bottom line - if you want to give an old system a new lease on life, browsers will get you right back onto square one, again, no matter what the underlying OS is. And I don't know of a good solution for that. And that kinda sucks, because you can no longer just give grandma an old system "just for email and Facebook".

Maybe far in the future webassembly will run in hardware, and then we'll just have webassembly machines with basically a minimal OS behind it.

But maybe that would be worse than the current state of things. Laugh | :laugh:

Real programmers use butterflies

I did just that with an old Windows 7 laptop over a year ago. It worked fine.

"That"?

Linux, or ChromeOS?

ChromeOS.

Now I'm curious. I thought Google went out of its way to prevent the average guy from just downloading an ISO and installing on random hardware. Has this changed?

Not sure what that has to do with the question.

Consider it its own question then. Has Google started making ISO files available for anyone to download and install on random hardware?

Sorry, I still do not know what you mean.

Do you not know what an ISO file is?

Here's one, but I'd rather download from a site owned by Google than..."this".

Yes, of course I do, and I have used them often over the years to make CD images of both Windows and Linux distributions. But I still do not know what point you are trying to make.

Really? I spell it out rather clearly a number of times throughout this thread.

I was under the impression that there was a point in time, at least initially, when Google apparently didn't want people to just download an ISO of the OS and install it on their own hardware; they'd rather have people buy Chromebooks with the OS preloaded (kinda like Apple goes it out its way to prevent people from downloading their x86-based OS and run it on non-Apple hardware).

I did not realize that this had changed (or was ever a thing to begin with). As per my last message, it does seem like they've relaxed the rules somewhat and you can download an ISO easily enough (I had never tried very hard), if you can find/trust the repositories for it.

I was just asking about that; I wasn't trying to "make a point".

Welcome to the Lounge