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.

Just brainstorming here:

A bloom filter could be used to build a more advanced re-post/cross-post
filter.   The bloom filter could track posts by the URL that they point to,
 and then store this bloom filter in localstorage.  This way RES could
filter out any link that has been seen before, and track pageviews over
time.

To filter images,  the entire image could be passed to to bloom filter.
All input goes though a message digest function,  so it doesn't really
matter the size of the input that is being tracked by a bloom filter,  this
won't impact memory usage.

On Tue, Dec 9, 2014 at 1:32 PM, Michael Brooks <firealwaysworks@gmail.com>
wrote:

> 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>
>> .
>>
>
>