Wikipedia:Reference desk/Archives/Computing/2013 September 22

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

September 22

array assignment with fewer characters

is there a way to do

 G[]={247570,280596,280600,249748,18578,18577,231184,16,16}

in fewer characters (same effect)? in C/C++

( I mean like maybe it's possible to assign one big hexadecimal number somehow or some other trick. We're just optimizing for source code space here, not readability.)— Preceding unsigned comment added by 89.132.116.35 (talk) 15:46, 22 September 2013 (UTC)

Are you concerned with this specific array full of magic numbers, or are you interested in a general solution? In either case, some of your numeric constants can be represented in hexadecimal, using fewer characters than in decimal. If you help us understand your motive, we might be able to offer a better targeted solution. Generally, it is not helpful to reduce source-code length as measured by number of characters. Nimur (talk) 15:48, 22 September 2013 (UTC)

Note that the original poster is talking about this code -- Finlay McWalterჷTalk 15:56, 22 September 2013 (UTC)

Ah, that makes much more sense in context. If this is an exercise in recreational program obfuscation, certain silly tricks might be in order, like replacing usage of the array by a simple polynomial; and so on. Some code obfuscation algorithms can actually optimize for smallest source-code size, and produce equivalently-functional, but shorter, source-code as output. After briefly scanning that code and its explanation, I doubt I could make it much shorter - at least, not without a lot of effort, and at the expense of a good deal of portability.

As a goofy example, you can (without loss of generality) represent a nine-element array of integers as a nine-term polynomial (or fewer, if you choose your constants wisely). This process is explained in detail in the curve fitting article. Of course, you have to design for minimal floating point error and assume the target computer rounds and calculates in the standard way, lest your integer constants get nudged off by a few bits when you calculate and cast them! It is probable that the representation of a nine-term polynomial is longer than a nine-element array of integer constants, but it depends on the coefficients you need. And there are alternatives to polynomials: in fact, a whole branch under the science of wavelet transformation is specifically dedicated to the mathematical study of minimal representations of arbitrary arrays of constants (signals) through the clever construction of transform domains. If a little error is acceptable, you can get orders-of-magnitude reductions in code size, which is (not coincidentally) the means by which modern image compression works. Now, in the example above, the numeric constants form a very low resolution bitmap image (with one bit per pixel), representing the positions of spheres in a world geometric model. Lossy compression is not great for low-bit-depth, low-resolution images. But if the world representation needed a longer array, the tradeoffs would start to look pretty good. Nimur (talk) 16:19, 22 September 2013 (UTC)

Wow, Nimur, what a detailed response. But this isn't the mathematics desk and I really was just interested in some kind of syntax in C/C++ or simple cheap trick that would shorten the assignment. For example, maybe there is a way to take a string "lkjr3lkjfsdf" and get those numbers, or hexadeciaml, or some other trick. The point is if you want to keep the array, but reduce the number of bytes to assign like so "={247570,280596,280600,249748,18578,18577,231184,16,16}" are there any cheap tricks to do so in C/C++? Things like hexadecimal, or character arrays, or anything else you can think of.... 178.48.114.143 (talk) 18:13, 22 September 2013 (UTC)

I've been playing on this problem for fun... and so far, I can not contrive a legal C program that uses correctly represents {247570,280596,280600,249748,18578,18577,231184,16,16} in fewer characters. I have tried a polynomial fit, and a recursive function, and a few variations of boolean and bitwise logic; it is easy to generate the constants, but the code takes more space. My next step is to try a Karnaugh map, as the process of trial and error is not yielding results. Nimur (talk) 22:55, 22 September 2013 (UTC)

Okay. I had to dig up espresso (it's been a long time!), because I wasn't able to minimize this one by hand. And I had to use this variant of the source-code from the University of Manchester (the antiquary Berkeley copy gave me compiler trouble); even the variant from Manchester used restrict as a variable name, which my C99 compiler treats as a keyword. (So, if you're following along at home, either disable C99 mode on your compiler, or replace all instances of "restrict" with some other variable name in unate.c).

Then I used this as my input function - (the espresso-representation of the array constants, and their array indices, in binary):

.i 5
.o 19
0000 -0111100011100010010
0001 -1000100100000010100
0010 -1000100100000011000
0011 -0111100111110010100
0100 -0000100100010010010
0101 -0000100100010010001
0110 -0111000011100010000
0111 -0000000000000010000
1000 -0000000000000010000

In other words, five input bits (for array index 0 through 8); and 19 output bits, because there are 19 bits in the longest represented numeric constant, the rest being "-" or do not care bits. I ran espresso on my input file ...which gave me output:

.i 5
.o 19
.p 9
-000- 0000000000000010000
0101- 0000100100010000001
0010- 1000100100000001000
0001- 1000100100000000100
0110- 0111000011100000000
0---- 0000000000000010000
0100- 0000100100010000010
0000- 0111100011100000010
0011- 0111100111110000100
.e

... in other words, a nine-element boolean logic expression; or, almost no reducible complexity whatsoever. Translating that back into the C programming language, I got a string that is significantly longer than the array of nine constants; the first few elements being:

((k>0&&k<8)?0x40:0)+((k^0xA)|k^0xB)?0x4881:0 // ... and so on; already too long by the third term, and painstakingly difficult to do correctly.

Now, we can't say we've proven that the string is best representable as a magic number sequence; in fact, it's nearly impossible to prove anything about the minimally-complex representation of a string; but we can say that we've thrown a lot of manual effort and computational horsepower at the problem and not made any headway towards a shorter string.

A few things I noticed during my experimentation: the a character and the e character glyph could be rendered slightly differently, such that one is a rotation of the other. The k glyph could be truncated so that it is only eight pixels tall, instead of nine. These single-pixel changes would make the entire problem much more tractable without affecting the human readability of the output. As it stands, neither I nor my computer were able to losslessly compress that nine-element array at all. The obvious solution is to represent it as the ASCII characters aek - but again, if you've been following along at home, you'll readily see why that representation, though shortening the constants-array, actually requires increasing the total length of the program. Nimur (talk) 00:11, 23 September 2013 (UTC)

I can easily represent the OP's array of magic numbers with different chracters, making the whole thing take up about 50% less space. However, as Nimur points out above, you would then need to write a function to turn that back into the magic numbers when you need to use them. Overall, that will make the program longer. If you had more magic numbers to represent in this way, you might eventually be able to get back the space you spent on the extra function. Astronaut (talk) 16:40, 23 September 2013 (UTC)

I can't look into the source code that uses it right now, but if it can be modified to handle rotating the bitmap, then it can be arranged as 19 8-bit characters rather than 9 32-bit words (only 19 bits were used of each word, and the 9th is discarded by realizing it is identical to the 8th, or just throwing it out because it doesn't change the result much). The values are:

char G[]={96,146,146,146,252,0,0,124,146,146,146,28,0,0,255,32,80,136,4};

or

char*G="`\x92\x92\x92\xfc\0\0|\x92\x92\x92\x1c\0\0\xff P\x88\x04";

That's too long, but a big part of the problem is all of the hex codes. The high bit is set a lot, which makes it unprintable in ASCII. Mirroring the order of the bits gives

char*G="\x06III?\0\0>???8\0\0\xff\x04\n\x11 ";

If you can refactor the code to work with data in that format, it is a bit smaller. Katie R (talk) 18:00, 23 September 2013 (UTC)

Thanks for the valiant effort, guys! 178.48.114.143 (talk) 22:58, 23 September 2013 (UTC)

I was just able to look at the link that Finlay McWalter linked earlier. I haven't tested it, but it looks like changing

if(G[j]&1<<k)

to

if(G[k]&1<<(8-j))

will let you use my second string representation. You add 4 characters there, but trim 15 off of the declaration of G. You also need to change the for loop to initialize j to 8 instead of 9, although this throws out the last row as mentioned in my last comment. Katie R (talk) 19:01, 24 September 2013 (UTC)

I need to stop looking back at this question. I enjoy esoteric/obfuscated/constrained programming far too much... Here's the idea that I just had for trimming more space. Drop the declaration of G entirely, then use this for the lookup:

if("\x06III?\0\0>???8\0\0\xff\x04\n\x11 "[k]&1<<(8-j))

I think that saves 18 characters overall. There are probably other bits of the code where characters can be trimmed, but trimming down that declaration has to be about the biggest. Another consideration is that the code was designed to fit on a business card, so some parts of it may have been written the way they are just to make it so endlines can fit in the right places. Katie R (talk) 14:44, 25 September 2013 (UTC)

How to handle very large arrays

Assume that I am using an interpreted programming language where array indexes start at zero. Given an array of millions of items and a function that does integer arithmetic, the program has to get array[f(x)-1] for a million different values of x. Would it be more efficient to give the array an empty zeroth element and have the program get array[f(x)] instead of repeatedly subtracting 1 from x? Is the answer different for different programming languages or are there other factors to consider (besides the additional memory for storing the empty zeroth element)? — Preceding unsigned comment added by 116.14.196.239 (talk) 19:47, 22 September 2013 (UTC)

It should be slightly faster to do that. That eliminates a million subtractions and wastes just one array element out of a million+. But the million subtractions might only take a fraction of a second anyway. The cost of that subtraction could be a lot less than the cost of the function, depending on what the function is. Bubba73 ^{You talkin' to me?} 20:26, 22 September 2013 (UTC)

Your way of thinking about this problem is 21 years out of date. For all but the tightest computational kernels on tiny windows of data, details of how many instructions are needed are in practice of secondary importance at best. For almost any operation on data sets with "millions of items", the overwhelming performance criterion of note is likely to be cache locality. Incrementing an integer held in a register is something CPUs are already ludicrously fast at, and its presence or absence will not yield a measurable time differential. -- Finlay McWalterჷTalk 21:46, 22 September 2013 (UTC)

Indeed, memory access is by far the dominant factor in most programs. For large arrays where many of the elements are zero (for example) you might benefit from using sparse array techniques. These can dramatically reduce the amount of memory needed for the array - and improve cache occupancy. The additional CPU time required to access them will typically be less than the cache hit improvement. But this depends dramatically on how much of your array is zeroes (or some other known value). SteveBaker (talk) 22:13, 22 September 2013 (UTC)

(ec) In fact, there is a specific instruction in most computer architectures for many variations on the theme: pointer dereference with offset is such a common operation, it usually executes exactly as fast as a pointer dereference with zero offset; and for all practical purposes, consumes exactly the same amount of energy per instruction (because the granularity of logic clock-gating is too coarse to turn off the pointer-offset ALU execution unit). In the Intel 64 instruction set, the pointer-offset can be 64-bits long, meaning that RAM is really randomly addressable. Every single pointer-offset can be anywhere else in memory; nowadays, there is no such thing as a short- or long- (alternately, near- and far-) pointer. Immediate-operands can be 64-bits long for free. If you want faster code, investigate algorithm changes first; and then micro-optimize by investigating commonplace instruction-set enhancements like Intel's AVX vector instructions (or the equivalent vector set for your favorite non-Intel processor); but don't imagine the array offset calculation is even relevant to the execution performance. It isn't. Nimur (talk) 22:20, 22 September 2013 (UTC)

Like noted above, it shouldn't make a difference. However, you did mention that it is an interpreted language. In that case it really depends on the nature of the interpreter, but I doubt it changes much. The best way to answer the question is to write a program that times the operation done both ways so you have hard data on the subject. The biggest rule about making tweaks for optimization is don't do it on a hunch - wait until you're actually seeing performance bottlenecks caused by the code, then use measurements to back up your choice of changes.. Katie R (talk) 14:10, 23 September 2013 (UTC)

• I don't really trust any of those answers. If the language is totally interpreted on the fly -- i.e., each line of code has to be reparsed every time it is encountered -- then parsing is likely to be the most important time-factor. Looie496 (talk) 17:57, 24 September 2013 (UTC)

If the interpreter is well-engineered, it will either pre-compile/pre-parse; or use a just in time compiler or similar intermediate representation. For example, CPython, Java HotSpot, and MATLAB have included these optimizations for many years. Only a naively-designed interpreter will re-lex the input text at each loop iteration.

Ultimately, the performance problem is not bottlenecked by calculation of a data element's address in memory. In languages like python, performance is bottlenecked because the memory is laid out inefficiently - large, complex data types are used to provide high level language features wrapping each primitive data element. This is intentional: a python programmer cannot* and does not want to manage memory at the logical or physical level. Instead, higher language abstractions of data structures are used. So, an array in python is not a contiguous chunk of memory treated as a sequence of primitive data types; it is really a special type of linked listlist of pointers with indexing; you can see what it looks like in memory by consulting the Python-C language binding reference (for the canonical reference implementation of the interpreter). if you write software wherein performance is actually tied to memory management and layout, high-level abstract languages are not the right tool for the job.

*Actually, using ctypes, a python programmer can manipulate data, within the logical memory space of its process; but native Python arrays do not do this.

Nimur (talk) 11:23, 25 September 2013 (UTC)

Python lists are arrays, not linked lists, but they are arrays of pointers (like a QList, but without efficient prepend()), so you have poor locality for the individual elements. (This could in theory be true only of CPython; the closest thing I could find to documentation that requires it is CPython-specific.) --Tardis (talk) 12:56, 25 September 2013 (UTC)

Thanks. I looked at the object representation and saw pointers to structs, and jumped the gun calling it a linked list. It is in fact a growable array of pointers to structs. That is a subtle but very important correction. Nimur (talk) 17:43, 25 September 2013 (UTC)

Cpython implements the abstract list type, as you describe, as an array of object pointers. Jython is very similar - it uses a java.util.ArrayList (in jython/src/org/python/core/PyList.java) which internally also uses an array of pointers. But Jython has a crucial difference, at least when running on HotSpot - HotSpot's collector reorders the heap based on referential locality, with the intention of improving cache performance. Similarly IronPython, which runs on the .NET runtime, uses an array of object references (IronPython/Runtime/List.cs); I think the CLR also reorders objects in memory with an eye to improving cache hit statistics. -- Finlay McWalterჷTalk 13:09, 26 September 2013 (UTC)