linux-kernel - Re: [PATCH] Add generic exponentially weighted moving average function

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-Id: <201010181227.06877.br1@einfach.org>
Date:	Mon, 18 Oct 2010 12:27:06 +0900
From:	Bruno Randolf <br1@...fach.org>
To:	kevin granade <kevin.granade@...il.com>
Cc:	linux-kernel@...r.kernel.org,
	Randy Dunlap <randy.dunlap@...cle.com>,
	akpm <akpm@...ux-foundation.org>
Subject: Re: [PATCH] Add generic exponentially weighted moving average function

On Fri October 15 2010 22:55:23 kevin granade wrote:
> >> This has a scaled up copy of the moving average, which reduces the
> >> available range for the average to MAX_INT/(AVG_FACTOR*num_samples)
> >> instead of +/- MAX_INT, is that acceptable?  Even if it is, shouldn't
> >> it be documented?  For example, with num_samples = 10, it will roll
> >> over to a negative value if the average exceeds 214,748.  This seems
> >> like a potentially surprising outcome.
> > 
> > Yes. I'll document this in the next version of the patch. Or should I use
> > 64bit for the internal representation?
> 
> If you don't expect the size or speed impact to be significant, it
> seems like just throwing a bigger number at the problem might be the
> better option.  That will move the rollover to MAX_INT/AVG_FACTOR,
> unless you also make AVG_FACTOR 64bit, which will promote all of the
> multiplications to 64bit and provide full MAX_INT range for input and
> output.

Honestly, I don't know about the speed impact of using 64 bit vs. 32 bit. 
I do know however, that the averaging function needs to be called quite often, 
where I want to use it, so performance could be an issue. And in my case the 
values are low enough so rollover is not a problem - but obviously I want to 
make this generally useful.

> I couldn't find anything that clearly indicated what the expected
> precaution is in this case.  It probably isn't an issue now that I
> understand that samples is intended to remain constant.  I initially
> thought samples would scale from 1 - n as you were initially "loading"
> samples into the structure, but now I understand that samples remains
> at n throughout the process.

I will work on the description.

Thanks,
Bruno
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/