String pooling in gcc with PROGMEM

Log in or register to post comments
Go To Last Post
7 posts / 0 new
Author
Message
kbosak
kbosak's picture
Level: Hangaround
Joined: Wed. Jan 30, 2008
Posts: 168 View posts
Location: Wroclaw, Poland
#1
Posted by kbosak: Fri. Oct 9, 2009 - 11:13 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hi,
My flash is really 99% used and I can save some 20KB
by using string pooling in A VERY IMPORTANT ;-) real-time system with interactive console (the strings are variable names, some 8...25 chars long (max 80 long)).
Of course all is using PROGMEM already.
Now the question is how to force it. I have found no option for that in gcc and it doesn't appears it is already done during compilation, even if I have several occurrences like:
VARNAME_A
VARNAME_A_MIN
a perfect scenario for suffix-based pooling.
So far I use PSTR macros but I can rewrite that easily.
Next step would be to put ALL strings (including error mesgs) to a pool.

I wonder if gcc can do this at all.
Anybody got custom codes for that?
I considered bit-rating strings at 6bits, but minor gain (only 25%).
Before I put LHA on it, would be nice to know what to try in an evening?

Tags:

Tools, Compilers and General Programming
Top
ka7ehk
ka7ehk's picture
Level: 10k+ Postman
Joined: Fri. Nov 22, 2002
Posts: 20640 View posts
Location: Tangent, OR, USA
Posted by ka7ehk: Fri. Oct 9, 2009 - 11:41 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Why not have a string "VARNAME_A" and one "_MIN". That will achieve your pooling, won't it?

I really doubt that there is any way to get the compiler to create the pools.

Jim

Jim Wagner Oregon Research Electronics, Consulting Div. Tangent, OR, USA http://www.orelectronics.net

Top
glitch
glitch's picture
Level: Raving Lunatic
Joined: Sat. Jan 12, 2002
Posts: 8710 View posts
Location: Canada
Posted by glitch: Sat. Oct 10, 2009 - 12:28 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Suffix based pooling is very difficult, because you don't know where to stop, as you can no longer rely on the null terminator. Prefix pooling is easier to implement. In either case you will need to do this manually.

Alternatively, you can look at doing some form of token based compression.

Writing code is like having sex.... make one little mistake, and you're supporting it for life.

Top
kbosak
kbosak's picture
Level: Hangaround
Joined: Wed. Jan 30, 2008
Posts: 168 View posts
Location: Wroclaw, Poland
Posted by kbosak: Sat. Oct 10, 2009 - 11:02 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
Why not have a string "VARNAME_A" and one "_MIN". That will achieve your pooling, won't it?

because there are ... 415 of them.
in many combinations, like OUTPUT_ INPUT_ MIXER_ etc.
Also I am looking for a general solution.
I am about to roll my own.

Top
david.prentice
david.prentice's picture
Level: 10k+ Postman
Joined: Sat. Feb 12, 2005
Posts: 29412 View posts
Location: Wormshill, England
Posted by david.prentice: Sat. Oct 10, 2009 - 11:35 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Just tokenise them, and let your output routine expand the tokens.

If you have duplicate strings, you can expect these to be reduced to a single copy. But you will have to read a lot of documentation to see how. Or perhaps pre-process the generated code yourself.

It is very unlikely that anything will give two entry points for "Prentice" and "David Prentice". And no way could you get "David" as a separate string.

David.

Top
kbosak
kbosak's picture
Level: Hangaround
Joined: Wed. Jan 30, 2008
Posts: 168 View posts
Location: Wroclaw, Poland
Posted by kbosak: Mon. Oct 12, 2009 - 09:17 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

It reminds me gangsta movies: 'Yo TOKEN to me?'

What could be the name of the process when I need to extract all common tokens of length at least N from given
pool of stings? The complexity can be N^4, I don't care.

Top
theusch
theusch's picture
Level: 10k+ Postman
Joined: Mon. Feb 19, 2001
Posts: 39611 View posts
Location: Wisconsin USA
Posted by theusch: Mon. Oct 12, 2009 - 02:28 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hmmm--Especially if the pool of strings is fixed (at least for a "run"), then a LEX-like state machine might be the fastest and might even be the smallest? (I guess the "smallest" might depend on the particular mix.) We used to do that on small microcomputers many years ago and it was the smallest way for sets of keywords.

Lee

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

Top