Lower RES Memory usage!

I got a new Microsoft Surface,  and the memory usage on RES is too much for the poor tablet.  So,  I decided to fork RES and see if I can reduce memory overhead for loading new pages.   If this patch goes well,  I'd like to further reduce RES's memory usage. 

This patch could use more testing.  Loading 10 pages with the current RES takes roughly 804M or ram,  after this patch the page consumed 764M with the same dataset.  Still needs more work,  but there is a noticeable reduction in memory usage with normal browsing habits.

Improvements:
- A bloomfilter is the most efficient way of keeping track of dupes.  A bloomfilter doesn't need to store the full string in order to keep track of uniqueness.  Additionally,  insertion into a bloom filter is always O(1), where as dictionaries need to be expanded when they become full.

-  "Hiding" elements with CSS doesn't make them go away.  These elements need to be deleted properly to free up memory. Hiding elements lead to a **nasty** memory leak.  Reddit has enough re-posts,  there is no need for RES to introduce duplicates to the feed.

Bloom filters have a significant advantage over dictionaries for the
purpose of identifying duplicates.  Dictionaries are very inefficient in
terms of space.  In order for a dictionary to guarantee an O(1) insertion
time,  it must be half empty,  when a dictionary become more than half-full
it will undergo an expansion,  which consumes more CPU and memory. To add
to this overhead,  the dictionary must also store each element as a string.

This bloom filter is taking up a total of 958505 bits,  or about 1.1
KByte.  No strings are stored in bloomfilter,  so that is ~1.1KB for the
life of the page load.



On Tue, Dec 9, 2014 at 1:05 PM, Andy Tuba <notifications@github.com> wrote:

> In lib/modules/neverEndingReddit.js
> <https://github.com/honestbleeps/Reddit-Enhancement-Suite/pull/1844#discussion-diff-21558020>
> :
>
> > @@ -101,10 +97,16 @@ modules['neverEndingReddit'] = {
> >  	go: function() {
> >  		if ((this.isEnabled()) && (this.isMatchURL())) {
> >  			// modified from a contribution by Peter Siewert, thanks Peter!
> > -			if (typeof modules['neverEndingReddit'].dupeHash === 'undefined') modules['neverEndingReddit'].dupeHash = {};
> > +			// bloom filter to store 100,000 elements with a .01 failure rate.
> > +			// http://0pointer.net/blog/projects/bloom.html
> > +			// m = -n*ln(p)/(ln(2)^2)
> > +			// m ~= 958505
> > +			// k = 0.7*m/n
> > +			// k ~= 7
> > +			if (typeof modules['neverEndingReddit'].bloomfilter === 'undefined') modules['neverEndingReddit'].bloomfilter = new BloomFilter(958505,7);
>
> One concern: ROI on adding Yet Another Library. Do you have a sense for
> when the bloom filter has better performance, memory/speed, compared to the
> plain dupeHash dictionary; and if that offsets the cost of loading the
> library?
>
> —
> Reply to this email directly or view it on GitHub
> <https://github.com/honestbleeps/Reddit-Enhancement-Suite/pull/1844/files#r21558020>
> .
>