Finding out how much memory was allocated

When allocating memory the system will often allocate more memory than you requested because it needs to align the memory to a boundary, or the memory has become fragmented. On many platforms malloc has propriety extensions which allow you to determine how much memory was /actually/ allocated. This can be useful, if for example the memory is being used as a buffer and you want to make use of that “spare” memory. It’s also a useful debugging tool, giving you some idea of the overhead involved in your allocations. This is particularly important if you’re allocating a lot of small memory blocks.

BSD systems use the extension malloc_size, Linux uses malloc_usable_size, they operate the same way and there are examples below. My Macbook running Snow Leopard seems to allocate upto an additional 511 bytes at times. My Linux box seems to allocate at most an additional 24 bytes, this is for allocations of up to 100K. Of course, either system could be lying to me, the true overhead could be higher.

It looks like the malloc_size functions can also be used to figure out if a particular pointer points to the start of a valid malloc’d memory block too. If you pass it an address within a memory block it appears to return 0 (I should imagine this works for unallocated regions too) malloc_usable_size on Linux seems to dislike being given non-word aligned addresses (adding 1 to a valid address gives random values, adding 4 appears to return 0 for pointers in, but not at the start, of the block).

Notes

Mac Source code and output:

#include <stdlib.h>
#include <malloc/malloc.h>

#include <iostream>

using namespace std;

int main() {

  for(int n=0;n<100000;n++) {
    int randsize = rand()%100000;

    void *ptr = malloc(randsize);

    cout << "requested: " << randsize << " allocated: " << malloc_size(ptr) << " extra " << malloc_size(ptr)-randsize << endl;

  }
}
&#91;/sourcecode&#93;

&#91;sourcecode language="bash"&#93;
g++ testmalloc.cpp
macbook:~ new299$ ./a.out | awk 'BEGIN{max=0;}{if($6 > max) max = $6;}END{print max}'
511

Linux:

#include <stdlib.h>
#include <malloc.h>

#include <iostream>

using namespace std;

int main() {

  for(int n=0;n<100000;n++) {
    int randsize = rand()%100000;

    void *ptr = malloc(randsize);

    cout << "requested: " << randsize << " allocated: " << malloc_usable_size(ptr) << " extra " << malloc_usable_size(ptr)-randsize << endl;

  }
}
&#91;/sourcecode&#93;

&#91;sourcecode language="bash"&#93;
$ ./a.out | awk 'BEGIN{max=0;}{if($6 > max) max = $6;}END{print max}'    
24

Paradoxia

I like paradoxes I think they tell us something meanful about the nature of logic. Here are the most succinct paradoxes I know of. If you have any more please leave a comment.

Berry’s paradox: The smallest number that can not be expressed in less than 20 words.

Russell’s paradox: Does the set of all sets that do not contain themselves, contain itself?

The liar paradox: This statement is untrue.

Quine’s paradox: “Yields falsehood when preceded by its quotation” yields falsehood when preceded by it’s quotation.

Unknowable truths

Godel’s incompleteness theorem is one of the most important and beautiful results in Computer Science. It tells us that even if we know exactly how a system is constructed there are statements about that system which are true, but we can never prove. They are in some sense unknowable truths.

However the usual presentation of Godel’s theorem is complicated and unwieldy. I could never really get my head around it, or find the time to dedicate to doing so. Even after gaining the jist of it, Godel’s description doesn’t leave me with the sense of awe that it perhaps should.

There is however another, less well known, description formulated in terms of Kolmogorov Complexity. It’s simple, beautiful, and certainly leaves me with a sense of awe. It somehow feels much more like a proof ‘should’. And runs as follows [1]:

1. Let x denote a finite binary string. We write “x is random” if the shortest description of x is at least as long as x. That is, we can’t write a computer program to generate x, that’s shorter than x. It’s incompressible.

2. We can see by a simple counting argument that there are random strings of every length. See note 2.

3. We have a language (formal system to use the precise terminology). In that language we can make statements like ‘x is random’. Now, suppose we can describe that language (F) in f bits of data. For example, this could be the number of bits required for an exhaustive description of the textbook ‘the language of F’. F can be a complicated language, but it must be consistent. No statement in F can be both true AND false, and only true statements can be proven to be true using F.

4. Now we’re going to show that there are statements in F which are true, but we can’t prove them ! Truths which exists that we can never know. We so this by contradiction. Given F we can start to exhaustively search for a proof that some string (which is a lot bigger than f) is random, and then print it when it’s found.

But wait! If you can prove it’s random it can’t be random! Why? Because the procedure to print it only required f + log n bits of data. Which is much smaller then n. Therefore we’ve proven something true, which is not true. Our language F is not consistent, and our axiom is violated.

So in short, you can have a system that’s consistent (things you can prove to be true, are really true) or a system which contains true statements but you can never know they are true…

I think it’s a stunning result! It tells us that whatever logical tool you use to look at the universal you will still fail to understand it completely. We are in some sense doomed to live in a state of unknowing, and must make peace with a certain degree of confusion.

——

Note 1: This form of the proof can be found on page 5 of “An Introduction to Kolmogorov Complexity and Its Applications”. Though I’m not sure that it originates here.

Note 2: That’s because there are 2^n strings of length n and sumof 2^(n-i) for i=1 to n-1 strings of length n-1 or smaller. As the number of strings of length n-1 is less than the number of strings of length n and our computer programs can be expressed as binary strings. It’s clear to see that there can’t be a 1 to 1 mapping between strings of length n and programs of length n-1 or less. There must be strings of length n with are random or ‘uncompressable’.

AOL Search Data Leak

In 2006 there was a “leak” of AOL search data. A large set of anonymized search queries was released publicly by AOL for research purposes. AOL however quickly realised that the data was a public relations nightmare, and that some users could be deanonymized though their search queries. The dataset was removed from their website, and the incident lead to the resignation of the CTO of AOL. Anyway, the dataset is still freely available on the internet and I’m interested in playing with it a little.

First of all I want to pull out the top search queries. UNIX sort and uniq handle this quite well as shown in the Notes section. Here are the top 50 queries:

1 711111

2 233670

google
3 98713

ebay
4 91234

yahoo
5 69314

yahoo.com
6 61890

mapquest
7 55832

google.com
8 54985

myspace.com
9 51433

myspace
10 30835

www.yahoo.com
11 30045

www.google.com
12 28185

internet
13 21353

http
14 20046

www.myspace.com
15 19578

map
16 19381

weather
17 18577

my
18 18560

ebay.com
19 16191

bank
20 15940

american
21 14512

pogo
22 14063

hotmail
23 13824

msn
24 13575

ask
25 13521

craigslist
26 13294

hotmail.com
27 12825

dictionary
28 12512

yahoo
29 11877

msn.com
30 11757

mycl.cravelyrics.com
31 11091

bankofamerica
32 10360

mapquest.com
33 10158

walmart
34 10126

my
35 10117

ask.com
36 9943

tattoo
37 9530

.com
38 9059

southwest
39 8926

myspace
40 8906

white
41 8510

maps
42 8342

sex
43 8315

porn
44 7791

mailbox
45 7714

home
46 7709

www.google
47 7615

fidelity.com
48 7506

pogo.com
49 7459

target
50 7372

match.com

Notes

wget http://www.atrus.org/hosted/AOL-data.tgz
tar xvzf AOL-data.tgz
for i in ./user*;do sed '1 d' $i >> aol_all.txt;done
awk 'BEGIN{FS="\t";}{print $2}' aol_all.txt | sort | uniq -c | sort -n -r -k 1 > aol_all.txt.top
head aol_all.txt.top -n 50 | awk 'BEGIN{n=1;}{print "<tr><td>" n "</td><td>" $1 "<td>" $2 "</td></tr>";n++;}'