Explosive RAM usage

[linas]

@ampli For your entertainment... I've been chasing something that feels like a mem leak, but isn't. I'm starting to understand it; I don't quite completely, so this is a developing story.

During parsing, I'm seeing memory consumption shooting up to 20GB, 50GB, 100GB RAM -- just outrageous RAM usage. Feels like a mem-leak, right? But its not. I'd hunted for mem leaks before, in discussion #1373 and there aren't any.

Ran a nice tool called heaptrack to collect a malloc/free trace. It also confirms that there are no memleaks. It does show, however, a "peak use" of 15GB (on a small dataset) in make_choice() in the amount of RAM Parse_choice. So I printed out how many of these get alloced per sentence. I'm also tracking the time to parse, and the number of disjuncts (after pruning). I made some graphs. It's interesting.

But first: some comments about the dictionary: It's unusual: it consists only of links between word-pairs, with a cost on each word-pair. When the parser asks for word expressions, the dict finds every possible word pair involving that word, and creates an expression of four optional connectors to the other word in the pair. The cost on that expression is the sum of the costs on the links. That's the word expression.

The result of parsing with this expression is called a "minimum spanning tree parse"; the final parse is the one that minimizes the total cost of all the links between word-pairs.

So, for example, parsing "this is a test", the pair (this, is) gets an autogenerated link type A and (this, apple) gets B and (this, cat) gets C ...many thousands. (is, test) gets P and (is, dog) gets Q ... so the word expression for is is created as

{A- or B- or C- or ...} & {A- or B- or C- or ...} & 
   {P+ or Q+ or ...} & {P+ or Q+ or ...}

so clearly this is very large. But .. not a problem. Expression pruning and power pruning chops this down to size in a few milliseconds; its very impressive how fast these are.

This leaves me with sentences that have 10K to 30K disjuncts in them, total. (All of my "sentences" are exactly 9 words long). Now, on to counting and building parse choices... see below.

[linas]

Parse time goes as the square of the number of disjuncts:

The number of struct Parse_choice alloced, vs number of disjuncts in the sentence:

Each struct Parse_choice is 96 Bytes.

Note the vertical scale. The right-most data cross is at 15 GBytes, which matches the max RAM usage for Parse_choice that heaptrack reported. So it looks like all the evidence matches up. Case closed.

The remaining work is to figure out how to put a cap on this, so that I can avoid RAM consumption explosions. Maybe resources.c ...

Raw data and graphs are in https://github.com/linas/link-grammar/tree/r18-overflow/link-grammar/parse

[ampli]

The right-most data cross is at 15 GBytes, which matches the max RAM usage for Parse_choice that heaptrack reported.

I have a branch that tries to reduce the memory consumption of the parse-set data by reducing the data structures. I have not measured how much it saves. In any case it will increase the CPU and memory efficiency, so I will try to see if I will be able to convert it to a PR in a timely manner.

Before doing that, I would like to finish a PR that reduces the number of unsane linkages. It reduces the huge number of unsane linkages in amy, especially after applying your recent regex suggestion (that generates alternatives on splits). But we saw that even English sentences may have a high ratio of unsane linkages even from a single occurrence of a a word in the form of xyz.. This also has a potential to the parse-set memory but I don't know if it applies to the dict/sentences you used in your test.

The remaining work is to figure out how to put a cap on this, so that I can avoid RAM consumption explosions. Maybe resources.c ...

Do you want to just abort handling a sentence in such a case? In any case, you can accumulate the size of the allocated pools and bug data structures (and ignore the rest) for such a cap.

Another important location of wasted memory is Table_connector. The its memory cap is currently 2^34 GB pointers = 256GB for sentences with many millions of disjuncts. It is not reduced between sentences. I guess that in practice its gets to 2^31 pointers.
To that you need to add the hashed buckets. However, note this from count.c:
#define MAX_TABLE_SIZE(s) (s / 10) /* Low load factor, for speed */
This means max. 10% loading. If you would allow 30% loading you could maybe save much memory in exchange for a few percents of slowness. But since it is not reduced (the saving of repeated allocations saves ~20% CPU) one complex sentence is enough to ruin this saving.

For monitoring the usage and size of Table_connector, the is in count.c:
//#define DEBUG_TABLE_STAT
If you define it, and invoke link-parser with -verbosity=5,debug=count.c, you get this Table_connector monitoring.
Also note -verbosity=104, to monitor the memory-pool usage.

BTW, in the last weeks I started to investigate the construction and use of the parse-set to find ways to optimize it.

[linas]

unsane

I'll try to graph unsane as well, see what happens.

Do you want to just abort handling a sentence in such a case?

I don't know. Any ideas? It seems to be fast to count the number of disjuncts, and if this number is too high, then we can skip parsing entirely. BTW, the parse-time timeout applies only to counting; there isn't any such check for creating linkages. But, for me, I set max linkages =15K, and then, building the linkages takes about ten times longer than counting! (and computing linkages does not do the parse-time timeout check)

MAX_TABLE_SIZE

I'll collect data on table connectors. Based on earlier results, I assume that the number of disjuncts will be a superior predictor for the needed tablesize, and so init_table() can be replaced with something that is derived from that.

I'll also repeat this, for pandp-union, fixes, fixes-long and failures, to see if the scaling results still hold there, or it they are peculiar to MST parsing. Might take a while.

[linas]

Here is another: the number of parse-set buckets allocated as a function of the number of disjuncts in the sentence. These are the buckets in the x_table, set up in extractor_new() in extract-links.c

What is interesting here is that the number of buckets goes as the 1.5 power of the number of disjuncts. So .. neither a square nor linear, but exactly in between ... how surprising!

Somewhat upsetting is that the predictive power of the number of disjuncts starts failing when #djs is greater than about 40K -- note that just past 40K, there are some cases with 1024 buckets (the minimum in extract-links.c) and also some huge ones -- over 30 million in that one cross.

Anyway, as a result of this, I plan to change the x_table_size calculation to be based on disjuncts and not on the number of words in the sentence. (But I suppose I should repeat these experiments w/ the English dict, see what happens there...)

[ampli]

Anyway, as a result of this, I plan to change the x_table_size calculation to be based on disjuncts and not on the number of words in the sentence.

I can make it dynamic as I did with Table_connector in count.c. In that case, extractor_new() would only determine the initial size of x_table_size (which will start relatively small).

[linas]

can make it dynamic

Well, yes, but you'll want my scaling coefficients; e.g. that green line is actually 0.03 * ndj**1.5 .. also I want to repeat all this for the English dict to see if it still holds there.

The most useful thing to immediately would be to cache the total number of disjuncts in Sentence, so it can be used for the counting table.

[ampli]

The most useful thing to immediately would be to cache the total number of disjuncts in Sentence, so it can be used for the counting table.

It is Sentence::num_disjuncts.

[linas]

But if you men the pool_alloc_vec stuff, sure, that would be great. I don't quite understand what is happening there.

[ampli]

But if you mean

To which thing I said do you prefer? (I can add explanation comments.)

[linas]

Here is how the number of the number of table-connectors scales with the number of disjuncts. The graph stops at exactly 30K disjuncts; I put in a hard-stop there, because otherwise parses take too long. BTW, to measure this, I did a pool_delete(sent->Table_connector_pool); after every sentence.

Two lines, one with power of 1.2 and one with power 1.4 .. these are eyeballed fits.

---

Given the earlier results that pex->Parse_choice_pool is much much larger -- its huge, for me-- it should probably pool_reuse() that one, too. FWIW I set linkage_limit=15000 but I don't believe that the size of pex->Parse_choice_pool depends on linkage_limit, but I will check.

[ampli]

pex->Parse_choice_pool is much much larger -- its huge

To be investigated...

it should probably pool_reuse()

We can even try pool_reuse() over sentences, in a try to reduce allocation costs and fragmentation.

[linas]

To be investigated...

I'll post english and russian soon

We can even try pool_reuse() over sentences

Sounds good to me. Can you do that? I will make some very basic changes, given the size estimates, "real soon now" .. today or tomorrow. I'm eager to get the rest of my project working, and this stands in the way.

[linas]

BTW the code I am using is in the given branch, so you can run it if you wish.

[ampli]

We can even try pool_reuse() over sentences

Sounds good to me. Can you do that?

I guess so.

[ampli]

in the given branch

It seems I missed something. Which one?

[linas]

Branch r18-overflow ... the data files and gnuplot files are in the parse directory. If you run gnuplot foo.gplot you'll re-graph my graphs. The datasets are slightly large than what I originally posted, so there will be some (un-noticable) differences.

https://github.com/linas/link-grammar/tree/r18-overflow/link-grammar/parse

BTW, English dict is very different ...

[linas]

OK, Here we go. English, Pride & Prejudice.

Number of disjuncts goes as the cube of the number of words in the sentence:

---

Number of linkages is super-exponential in the number of words. $N_{linkages} = w^{(0.1w)}$ for the curved line, and $w^{11}$ for the straight line.

---

Parse-time as a function of number of disjuncts is sub-linear: the power is 0.8! So this is very very different from the MST data, where parse time went as the square. Perhaps not surprising, given the nature of MST... but still.

Number of connectors vs number of disjuncts. This is the sum of left and right connectors on the words. The power is 1.17

---

Number of table connectors vs number of disjuncts. The table-connectors are pool_size(sent->Table_tracon_pool) in count.c

---

Same as above, except this is pool_num_elements_issued(sent->Table_tracon_pool) in count.c The horizontal lines above were due to the 16K block size.

---

Number of parse-choice alloced vs number of disjuncts. The power is 1.5 but that is not very trustworthy.

---

Same as above, except its number used: pool_num_elements_issued(pex->Parse_choice_pool) in extract-links.c The horizontal lines above are due to the blocksize of 1K elements.

---

Buckets vs disjuncts. The power is 1.17 .. I picked that because of the earlier result.

---

Same as above, but showing pool_num_elements_issued(pex->Pset_bucket_pool) in extract-links.c -- The horizontal lines above are due to the block-size being 1K

That's it. Next, I'll try to plot English & MST on the same plot ...

[linas]

Combined graphs. No comments.

---

"Table connectors" are pool_size(sent->Table_tracon_pool) in count.c

---

Same as above, but pool_num_elements_issued(sent->Table_tracon_pool) in count.c -- the horizontal lines are due to the 16K block-size, and the "third dataset" only has that variant.

---

"Parse choice" is pool_size(pex->Parse_choice_pool) in extract-links.c

---

"Buckets" is pool_size(pex->Pset_bucket_pool) in extract-links.c

[linas]

We have no direct control over the number of parse choices that get used. It is what it is. But still, its worth trying to understand how parse choices get use. The graphs below both show pool_num_elements_issued(pex->Parse_choice_pool) in extract-links.c For whatever reason, the MST parses require a lot more parse-choice structs. Also, graphing these vs number of disjuncts shows two very distinct behaviors: MST parsing is nothing at all like disjunct parsing. Don't know why. Perhaps there are too many links with a terrible cost being used. I will review this later.

It would be nice to find a scaling law that unifies these two. I attempted $N_d/\log(N_w)$ and $N_d/N_w$ and $N_d/N_w^{1.5}$ and $N_d/N_w^2$ and each looks better than the last, and the last one looks the best. Shown below.

[ampli]

It seems that after do_count() finishes, it is possible to find out an absolute upper limit for the number of parse sets and parse choices. However, I have not verified that. Currently, they will be much greater than the real value unless we find a way to filter out the false-positive ones (finding such "dead" entries while parsing in do_count() will save much memory). The idea is based on the count of the non-zero entries in Table_tracon (see table_stat) and table_lrcnt (for table_lrcnt, the calculation in free_table_lrcnt() is skewed and a slight fix in the memory-pool code is needed for not counting non-issued elements).

[linas]

Here is a graph showing number of parse choices vs number of expressions. That is, pool_num_elements_issued(pex->Parse_choice_pool) vs pool_num_elements_issued(sent->Exp_pool) ... It seems to be pretty clean, and can be used to provide an estimate/upper bound for the number of Parse_choice elts that will be needed. Done in #1415

[ampli]

I have an idea of how to memory-sare parse choice elements, just like parse set elements are shared through the x-table.
Currently, they cannot be shared because each has a unique value.
I thought of these data structures (typedefs omitted):

struct Parse_set_struct
{
   Parse_choice_desc *desc;
   ...
};
struct Parse_choice_desc_struct
{
   Parse_choice_desc *next;
   Parse_choice_lr *l_pc, *r_pc;
};
struct Parse_choice_lr
{	
   Parse_set * set;
   Disjunct    *md;           /* the chosen disjunct for the middle word */
   int32_t id;                /* the tracon (l_id for l_pc and r_id for r_pc  */
};

(What is now set[1] and set[2] will be in l_pc and r_pc, correspondingly.)
Of course, there is a question of how much sharing will be done (if any, I don't know even that) and what will be the CPU overhead.

[linas]

See #1419

[linas]

*Edited: I removed three graphs that were mistaken. Nothing depends on linkage_limit. *

For buckets, lets try graphing vs. disjuncts per word. This looks much better.

---

For the table_connectors, the MST-15K and MST 1.5K datasets use the same number of table connectors, (exactly?) To align English with MST, I multiplied by log(number of words) Why multiply? Why log? I dunno. Voodoo. Here's the result:

Above graph is for pool_size(sent->Table_tracon_pool) in count.c

[ampli]

According to my understanding, linkage_limit has no direct interaction with the connector table or Parse_choice.

For English, there may be an indirect influence due to sentences with a low density of linkages w/o PP violation. If linkage_limit is e.g. 1000, and the no-PP linkage percentage is very low, e.g. < 0.1%, then no good linkage will be found and the parsing will repeat with higher null counts and potentially bigger tables.

However, for your test dict, an influence of linkage_limit on the size of the connector table or the Parse_choice allocations doesn't make sense to me.

[linas]

Yes, linkage_limit has no interaction here. It was a confounder cause I accidentally graphed the wrong column, which confused things. Now all fixed.

[ampli]

Regarding the Table_connector table size, note that it is now a table of tracons, not connectors. The number of tracons is drastically smaller than the number of connectors and increases slowly with the number of disjuncts (if on a particular word, you add disjuncts that use the same tracons as previous disjuncts, then the number of tracons doesn't increase at all).

[linas]

OK. I might change the name to table_tracon or something similar. I like having easy-to-grep names.

I completely removed the graphs about the dependency on linkage-limit. So the "good news" of estimating sizes is gone. I'd made a mistake; I had plotted the wrong column! That means that once again, I don't know how to estimate the table sizes for the two linkage-related tables. That's bad....

[linas]

There are three other pools: sent->wordvec_pool, mchxt->mld_pool, mchxt->mlc_pool I don't know if these matter. Since I'm at it, I will redo and measure those too.

[ampli]

I don't know how to estimate the table sizes for the two linkage-related tables.

Maybe they are related to the number of tracons in the sentence.
There are LHS tracons (belonging to Disjunct::left) and RHS tracons (belonging to Disjunct::right), which are unrelated.
Their total number is held in count_context::table_lrcnt[dir]::sz (but note that by default table_lrcnt is NULL for very short sentences, see alloc_count_context()). dir==0 for LHS, dir==1 for RHS.

There are three other pools: sent->wordvec_pool

Its total count of iwordvec_pool vector elements is much less than the total number of tracons (LHS+RHS) multiplied by sentence length.
The sz values above are the sizes of table_lrcnt. Each element is indexed by tracon-ID and may point to a vector from wordvec_pool when the vector length is the number of words accessible from that tracon (see alloc_lrcnt_wv()).

mchxt->mld_pool, mchxt->mlc_pool

Elements from these pools are allocated in pairs (one from each pool). I guess they could be combined into a struct and allocated together. Also note that currently the longest match list is hard-limited to 512K elements (match_list_pool_size), and the program will abort if exceeded.

[linas]

Here is my "final" graph for the tracon hash table. This has linear bounds, used to support pull req #1403 Both an upper and lower bound is used.

---

Same as above. but showing actual used entries: pool_num_elements_issued(sent->Table_tracon_pool) in count.c (for pandp only, the other datasets didn't measure this.)

[linas]

More graphs.

This shows pool_num_elements_issued(sent->Exp_pool)

The sentence Exp pool is used before the disjuncts are built. We've got no prior size from which to estimate what the above could be. It is what it is. The only optimization I see here is to delete the Exp_pool earlier. Attempted in #1413 but that won't work.

However, the Exp_pool size could be used as an estimator for other things, e.g. the whacked behavior for parse-choices! Ah hah!

---

This shows pool_num_elements_issued(sent->Match_node_pool)

Maybe the Match_node_pool can be deleted earlier?

---

This shows pool_num_elements_issued(ctxt->mchxt->mlc_pool) from count.c

The MST pool_size is pool_size(ctxt->mchxt->mlc_pool)

Note the strange pathology at the upper right. Pool sizes get strangely large for some rare cases w/ MST parsing, when there are more than 25K disjuncts. Don't know why this happens.

---

Like above, except its MLC vs exp. The various lines are attempts to estimate the MLC pool size, and to place an upper bound on it (derived from the expression pool size). This is done in #1414

---

I have no clue what wordvecs are. This graph is weird and hard to understand it. The "poolsize" is pool_size(sent->wordvec_pool) while the "issued" is pool_num_elements_issued(sent->wordvec_pool) ... Apparently, the wordvecs get re-used for each word. Thus, the pool_num_elements_issued is the state of things, after the last word. Whereas pool_size is the max of all allocations for all words. Or .. something like that.

[linas]

@ampli Do you have any idea why parse-choices are appended to the tail? Here:

link-grammar/link-grammar/parse/extract-links.c

Lines 126 to 142 in 7951ed8

	/**
	* Put this parse_choice into a given set. The tail pointer is always
	* left pointing to the end of the list.
	*/
	static void put_choice_in_set(Parse_set *s, Parse_choice *pc)
	{
	if (s->first == NULL)
	{
	s->first = pc;
	}
	else
	{
	s->tail->next = pc;
	}
	s->tail = pc;
	pc->next = NULL;
	}

Seems to me we could chain to the head, and save a pointer in the bucket. If for some reason the order is important, it could always be reversed later? ??

[linas]

a bug somewhere

Among other things, the python test case is buggy, but that is not the entire explanation. I'm, still digging.

[ampli]

It is also possible to save about half of the memory in Parse_choice

I succeeded to reduce Parse_choice from 96 bytes to 48, at the expanse of increasing Parse_set from 40 to 56.
The saving is much more than the difference in sizes since there are many more Parse_choice instances.
I'm preparing now a PR. My test script encountered a problem due to the linkages with repeated multi-connector sequences that are now considered duplicates, so I added a patch to discard such sequences (eliminate_duplicate_disjuncts() discards the resulted duplicate disjuncts, if any). I will send it as a separate PR.

Things that I still need to implement and test for CPU overhead:

• Reduce Parse_set and Parse_choice each by a further 8 bytes.
• Use Parse_choice arrays (instead of lists) - another 8-byte saving.
• Don't save Parse_set() instances with first==NULL.
• Since a significant number of parse_set instances have only a single Parse_choice instance, include the first Parse_choice inside Parse_set.

The initial PR will be without these.

[linas]

I got rid of the tail pointer in #1407 It took me a day to figure out why the python spell-check was failing -- the unit test was bad. It set !spell=99 but !max-linkage=100 Since there are 122 linkages with the current aspell dicts, this went into random-select, and the desired spelling correction was not found.

[linas]

I'm leaving the house for a few hours, but then after that, I wanted to alter how x_table_size is set up in extractor_new(). However, I am concerned that this will clobber your pending pull-req above ... let me know if I should proceed, anyway? Care to send in your partially-finished pull req? If it passes the unit tests, it's good-enough for me :-)

[ampli]

I'll send it in a few minutes.

[linas]

The graph below will form the basis for estimating the x_table_size to be used in extract-links.c It measures pool_size(pex->Pset_bucket_pool) on the vertical axis. The fit is voodoo -- the upper bound on the number of buckets alloced is given by 0.5 * (num dj / sqrt(num words))**1.5 and I have no particular intuition why it would be that, instead of some other scaling law. Used in #1411

Below is the same graph, except this time, the actual number of buckets issued is graphs, instead of buckets alloced. Thus, the horizontal bars go away. The stepped black line is the result of taking the ceil of the size estimate, making the hash table size always be a power of two.

Below is the same graph as above, but now extended to smaller sizes. Huh. Go figure.

[linas]

Here's an alternative view of the above: It shows the number of used pset buckets, as a function of the number of expressions. The upper and lower counts are simpler, but not as tight.

[linas]

Time to wrap it up. More or less everything noted above has been implemented, except for a few ideas that don't see so important any more. -- #1406 and #1413 Lets remeasure parse time.

Above is just what it says it is. Several things that are notable:

• Parse time goes as the square of the number of disjuncts, at least for the MST case. This is perhaps not surprising, even expected, given the nature of what MST is.
• Time to extract seems to be consistently 3x larger than time to parse (count) at least for MST.
• The clock has 3 mS resolution accounting for the horizontal bars.
• There seems to be no timing difference between extracting 150 and 1500 linkages.

[linas]

The graph below explores the ratio of (time to extract) / (time to parse)

Notable:

• The ratio seems to be exactly 3, for MST, except for when it's 1.5. Why 3? Why 1.5? Are these accidents?
• There is no difference between extracting 150 and 1500 linkages (linkage-limit=150 and 1500 respectively.)
• The horizontal bars for Pride & prejudice are just ratios at the limit of clock resolution.

[linas]

Same ratio as above, but this time w.r.. time to parse (meaning, time to count, excluding time to extract).

This includes data from a linkage-limit=15K dataset, and finally we do see some dependence on the number of linkages extracted. But this is only for the fastest count times -- we can conclude the time to extract 15 linkages is well under 0.1 seconds.

The moire pattern for Pride & Prejudice is due to clock resolution. Despite this, it is clearly behaving very differently from the MST parses.

[linas]

Last but not least, confirm what we already know: time to extract is linear in the number of parse choices.

• The linkage-lim=15K data is not shown, because it adds nothing and clutters the graph.
• For MST, number of parse choices is quadratic in number of disjuncts, but we knew that already. Again, its quadratic due to the way that the MST disjuncts are constructed.
• MST and the conventional English dict behave very differently. We knew this before, but the partitioning here feels cleaner than the others.

[linas]

The End. I think I'm done. Once again, all code is in https://github.com/linas/link-grammar/tree/r18-overflow/link-grammar/parse *.dat, *.gplot and the *.png can be recreated from the gplot files.