iPhone Huge array/string - best practice question

Target Platforms Mobile
1

(Did look around before posting this…)

I have a fixed string of 240,000 characters which are really 29000 words. I’m selecting a random word from this list.

OK: I don’t really have it in use yet, since that’s my question: what suggestion does anyone have for my needs: to pick out a random word from a list of 29,000 words. What data structure?

240K isn’t too much, at least at first blush… but there may be limitations I don’t understand as a newbie.

I’m NOT dumping it into an array, on the theory that such would simply duplicate the amount of memory used, whereas a few lines of code will suffice to pluck the word from the ‘string’.

So, I guess, Q1 is: can I get there from here?
Q2: can I have a 250K string, or do I need to split it up?
Q3: or have I totally missed a better way to do this?

Outside of Unity, I’d do this with a SQLite DB in the doc folder, just to keep it from loading… but… ummm… er…

Just hoping someone here has some comments. Don’t need you to write my code for me (thanks for the offer ;-), but would sure like to pointed away from wasting my time! :slight_smile:

TIA

2

If access speed is your number one priority, I think a String Array would be your best bet.

From the Script Reference:

The following should be plenty fast for the iPhone:

var bigArray = new String[29000];

for (i=0; i<29000; i++){
	bigArray[i] = "collection";
}

Debug.Log(bigArray[Random.Range(0, bigArray.Length)]);
3

Note that you can use something like System.IO.Streamreader to read the words from a text file and set them to your array. So it’s only in memory once.

4

I don’t quite understand what StreamReader does. :?:

Is there some reason you need the actual string in the game? If not, you could use Split on it, then Trim to clean up the white space or whatever you have. Then, you can serialize that array with the shipping game (leaving the string itself only in your project folder), saving presumably 227 KB, and having the fastest possible search mechanism, as tonyd said.

5

Thanks tonyd and jessy… I appreciate the comments. Leaving aside speed (which isn’t particularly important in my case) I’m not sure I see the benefit to using an array (other than a few lines of code to access the data.)

Jessy: perhaps I’m missing something, but say I have the string “this is a string with some characters in it.” That’s 44 characters long. If I make a string array of it and assume 1 byte overhead per record, my array is 44 bytes long as well… so I don’t see the savings.

tonyd: if I just use the string, it’s also only in memory once.

Not arguing with you folks… just curious as to what it is I’m missing in your suggestions. My take is that if it eats up 250K of RAM, it will do so either as an array or as a string, eh?

Or… as I said, perhaps I don’t get what you’re saying.

In either case, thanks for your courteous replies! :slight_smile:

6

Strings are Unicode, 2 bytes per character

7

and… you’re saying that an array of strings is not Unicode?

8

No, but my numbers implied it. But I’m wrong, which is lame. And I’m having trouble finding info, but it may even be that each string needs a whole 4-byte int to store its index in the array.

9

I am saying each character in each string is 2 bytes, not one byte like you said. So a unicode string with 10 characters takes up 20 bytes plus the string class overhead.

10

Right. I understand that, thanks. I was trying to make a point about relative sizes, simply, and didn’t think that whether or not each character was one byte, or two, altered that point much.

Thanks, tho!

11

Actually, the reply was to Hoff, but your point is taken. While I’m completely new to Unity, I’ve been programming for 32 years… and I didn’t think that much had changed with the new environment! :slight_smile: (Arrays always have overhead, sometimes significant. It’s pretty hard to get more efficient than a binary stream (without something like hashing etc.)

12

Your arrays are taking up 580,000 bytes just to store the word “collection” 29,000 times. That doesn’t include the size of an empty string class itself, which is going to be at least 4 bytes, probably 8 bytes (pointer to buffer, and a length), so that is another 116,000 bytes. So your total heap used is about 700,000 bytes.

13

Thanks, Hoff… so, keeping it just as a string actually is more efficient, in terms of space used in memory, as I suspected.

Is there any way to force a string to ASCII? That would cut the requirements in half…

(Or, of course, maybe I just cut the size of the list in half. I don’t really -need- 29,000 words… 14K would do nicely… :wink:

14

I don’t think you can force them to ASCII :frowning: Pretty sure the string class itself is always Unicode.

If you know each character will always be 8 bit ASCII, then you could use byte arrays instead of strings, and just null terminate each one (so “collection” is 11 bytes). Then when you need to display it, convert it from ASCII to Unicode.

By the way, sizeof( string) == 4, not 8 like I assumed. So an empty string class takes up 4 bytes. But I forgot the fact that each string stored is NULL terminated.
So the true amount of memory would be

29000 * 4 (for the string class overhead)
29000 * 22 (the unicode text “collection” + a unicode null)

754,000 bytes total to store the unicode word “collection” in a string class 29,000 times.

Here is some info:
http://www.yoda.arachsys.com/csharp/strings.html

15

Thanks for the calculations Huff, and the definite size information about strings. My actual string size is about 240K, but I think I’ll cut that in half for the sake of the iPhone. My game won’t suffer for it.

I’ll keep the list of 29000 words for desktop or future use. Half or even a quarter will do, now that I think of it.

I appreciate your help and courtesy. Thanks! :slight_smile:

16

From your posts it sounds like you are trying to optimize the wrong problem.

As I understand it you have a text string, consisting of a word list of 29000 words, taking approximately 240KBytes of storage.

Are you worried about download size? Then optimize the word list, and expand in memory when loaded.

Are you worried about memory footprint on the iPhone? A word list of 29000 words, assuming it takes 240KBytes of storage would expand to around 500Kbytes in RAM if stored as a single Unicode string. ECMAScript/JavaScript/Unity’s version of Javascript stores strings in Unicode format because it runs on top of the Mono framework and Mono is Unicode by default.

If you read in your 29000 word list to an array, assuming it was stored as ASCII on the file system, taking up only 240KBytes, it would take up over 900KBytes of RAM with all of the overhead. Any other storage mechanism, such as a Hash, a List or some such would push that number somewhat higher too.

If you are concerned by the amount of RAM your application is using, unless you have a metric tonne of textures and other assets, the 750KByte difference you are talking is seriously neither here nor there.

Another caveat is that even if you store your word list as a single string, the moment you start doing any sort of string splicing on it, because strings are immutable on Mono and also in JavaScript, you will begin to incur a large overhead of heap allocations, possibly far more than if you had stuffed your entire word list in to an array.

You could come up with some clever jiggery pokery that treats the word list as constant binary data block of ASCII characters by storing the strings in a .DATA section of the binary, but this is JavaScript and you ain’t going to be achieving anything magical like that in a hurry unless you write an Objective-C/C++/C/Assembly language plugin to do it for you.

Sounds like confusion over memory footprint, and heap usage, compared to data stored in the file system, that or a severe case of premature optimization.

My recommendation, without knowing anything else about your project, read each line of the text file into an array or Hash or Dictionary or whatever your preference is that enables rapid look up. When you start running out of memory, then worry about where you can optimize.

If you are concerned about download size, then optimize your word list as it is stored on the file system accordingly.

My current word game loads a 300,000 word list from disk, taking up around 250KBytes of storage, which expands in to around 6MBytes in RAM, stored in a Dictionary (Hash). When I start running out of RAM due to large graphics requirements, that’s when I’ll start optimizing my word list, until then, I’m not worried about it.

  • From the person who once squeezed a hundred thousand word dictionary onto an 80KByte floppy disk for a word game on the BBC Micro Model B.
17

Well, I’m not actually splicing… just getting out a substring: pulling out one word. The words are separated by a hyphen. I pick a number between 0 and 240K, and starting at that point in the string, get the next 30 characters into a string. Then I parse out the first whole word in that string:

	     var j = UnityEngine.Random.Range( 0, 239515 );
	     var tempstr = wordlist.Substring(j,30);
	     j = tempstr.IndexOf("-",0);
	     var k = tempstr.IndexOf("-",  j+1);

	     word = tempstr.Substring(j+1,k-(j+1));

Is this causing “… a large overhead of heap allocations, possibly far more than if you had stuffed your entire word list in to an array?”

In my previous coding life, all of this would involve very modest heap use.

And… Thanks! for the thoughtful and detailed reply.

18

As a footnote: If you just store the word “collection” 29,000 times in an array of strings, and then test to see how much memory you are using, you actually just use the amount of memory required to store pointers and reference counters to the immutable string “collection.” On a 64-bit Windows 7 machine using .NET 4.0 this takes up 232,032 bytes of RAM giving you some insight in to how much an array of strings storing the same word over and over again will actually take up, or, 8 bytes per string reference, and 32 bytes for the overhead to store the array.

19

You are correct in your assumption that your solution should not cause unnecessary heap usage, and if I were doing this in Assembler/Pascal/Forth/C or even C++ (without a template library like Boost) I could say with some certainty how much heap would be used, and it would be negligible. However, this is .NET and consequently the normal rules that we have both learned over the past 32 years don’t always apply. A lot of stuff goes on behind the scenes giving you enough rope to shoot yourself in the foot with. You can see this when people load up a JPG image by allocating an ArrayList of integers to store each byte of the image (I’ve seen this in production code so many times.)

Yours is a unique solution to the problem. I like it. I do not know if that will cause a lot of heap usage. Let’s find out. Back in a moment.

In the mean time, here’s some dog food to contemplate.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace WordStorageThrowaway
{
    class Program
    {
        private static void ListMethod()
        {
            long startBytes = GC.GetTotalMemory(true);
            List<string> text = new List<string>();
            //string[] text = new string[29000];
            for (int i = 0; i < 29000; i++)
            {
                text.Add(String.Format("{0}", i));
            }

            long allocatedBytes = GC.GetTotalMemory(true);
            Debug.WriteLine(String.Format("List Method: {0}KBytes", (allocatedBytes - startBytes)/1024));
        }

        private static void ArrayMethod()
        {
            long startBytes = GC.GetTotalMemory(true);
            string[] text = new string[29000];
            for (int i = 0; i < 29000; i++)
            {
                text[i]= String.Format("{0}", i);
            }

            long allocatedBytes = GC.GetTotalMemory(true);
            Debug.WriteLine(String.Format("Array Method: {0}KBytes", (allocatedBytes - startBytes) / 1024));

        }
        private static void StringMethod()
        {
            long startBytes = GC.GetTotalMemory(true);
            string text = "";
            for (int i = 0; i < 29000; i++)
            {
                text += "a";
            }

            long allocatedBytes = GC.GetTotalMemory(true);
            Debug.WriteLine(String.Format("String Method: {0}KBytes", (allocatedBytes - startBytes) / 1024));
        }

        private static void ArrayCollectionMethod()
        {
            long startBytes = GC.GetTotalMemory(true);
            string[] text = new string[29000];
            for (int i = 0; i < 29000; i++)
            {
                text[i] = "a";
            }

            long allocatedBytes = GC.GetTotalMemory(true);
            Debug.WriteLine(String.Format("Array \"Collection\" Method: {0}KBytes", (allocatedBytes - startBytes)/1024));
        }

        static void Main(string[] args)
        {
            ListMethod();
            ArrayMethod();
            StringMethod();
            ArrayCollectionMethod();
        }
    }
}

And the results:

List Method: 1381KBytes
Array Method: 1351KBytes
String Method: 56KBytes
Array "Collection" Method: 226KBytes
20

oooohhh… another geek! :slight_smile:

Thanks! And the results you just posted are interesting. You were/are quite correct that the percent of additional overhead wasn’t worth worrying about.

I see we’ve both been at this a while… and the old habits formed from writing code to fit into 48 -K- die hard, don’t they? :wink:

I just cringe when I have bloated code. Point of pride, I guess.

Thanks for your interest. (And yes, it was my unfamiliarity with .NET and the fear of foot-injuries that prompted the post in the first place…)