FAQ
I have a table-based ln factorial function that is initialised with a
starting table which can be expanded (I may put a limit on the max size
at a later stage) by calls to lnFac() below.

At the moment the function is obviously not thread safe and I would like
to make it so. I had a look at using a sync.RWMutex, but the locking
looks like it will get tangled.

Any suggestions?

const tableLength = 10000

var lnFacTable = genLnFac(tableLength)

func genLnFac(l int) (table []float64) {
table = make([]float64, l)
lnfac := 0.

for i := 1; i < l; i++ {
lnfac += math.Log(float64(i))
table[i] = lnfac
}

return
}

func lnFac(x int) float64 {
if x < len(lnFacTable) {
return lnFacTable[x]
}

l := len(lnFacTable)
lnFacTable = append(lnFacTable, make([]float64, x-l+1)...)

lnfac := lnFacTable[l-1]

for i := l; i < len(lnFacTable); i++ {
lnfac += math.Log(float64(i))
lnFacTable[i] = lnfac
}

return lnfac
}


--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Search Discussions

  • Tamás Gulácsi at Apr 9, 2013 at 4:59 am
    lnFac and genLnFac does the same, that is the problem.

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Dan Kortschak at Apr 9, 2013 at 5:38 am
    There's not actually a problem. I can see why you think they do the same
    thing, and I could get away removing genLnFac, but that's really not
    what I'm asking about.

    lnFac returns the ln factorial of x and can be called by (in the
    proposed thread safe implementation) any number of parallel callers. At
    the moment this is not the case since a call past the end of the table
    will cause a race condition for another caller. genLnFac on the other
    hand is called once during initialisation.
    On Mon, 2013-04-08 at 21:59 -0700, Tamás Gulácsi wrote:
    lnFac and genLnFac does the same, that is the problem.

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Gulácsi Tamás at Apr 9, 2013 at 5:43 am
    For an x not in the table, ln does what gen would do with a big enough l.
    As I read and interpreted (possibly badly)
    2013.04.09. 7:38, "Dan Kortschak" <dan.kortschak@adelaide.edu.au> ezt írta:
    There's not actually a problem. I can see why you think they do the same
    thing, and I could get away removing genLnFac, but that's really not
    what I'm asking about.

    lnFac returns the ln factorial of x and can be called by (in the
    proposed thread safe implementation) any number of parallel callers. At
    the moment this is not the case since a call past the end of the table
    will cause a race condition for another caller. genLnFac on the other
    hand is called once during initialisation.
    On Mon, 2013-04-08 at 21:59 -0700, Tamás Gulácsi wrote:
    lnFac and genLnFac does the same, that is the problem.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Dan Kortschak at Apr 9, 2013 at 5:45 am

    On Tue, 2013-04-09 at 07:43 +0200, Gulácsi Tamás wrote:
    For an x not in the table, ln does what gen would do with a big enough
    l.
    Yes, absolutely. The code is only differentiated for clarity.

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Rémy Oudompheng at Apr 9, 2013 at 5:47 am

    On 2013/4/9 Dan Kortschak wrote:
    I have a table-based ln factorial function that is initialised with a
    starting table which can be expanded (I may put a limit on the max size
    at a later stage) by calls to lnFac() below.

    At the moment the function is obviously not thread safe and I would like
    to make it so. I had a look at using a sync.RWMutex, but the locking
    looks like it will get tangled.

    Any suggestions?
    The RWMutex looks like the natural thing to use.

    Rémy.

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Dan Kortschak at Apr 9, 2013 at 5:49 am

    On Tue, 2013-04-09 at 07:47 +0200, Rémy Oudompheng wrote:
    The RWMutex looks like the natural thing to use.
    Yeah. I initially thought so, then got tangled, but I think I have
    something that works now:

    func lnFac(x int) float64 {
    tableLock.RLock()
    l := len(lnFacTable)
    if x < l {
    defer tableLock.RUnlock()
    return lnFacTable[x]
    }
    lnfac := lnFacTable[l-1]
    tableLock.RUnlock()

    // New section to prevent excessive table growth.
    if x > maxTableLen {
    for i := float64(l); i <= float64(x); i++ {
    lnfac += math.Log(i)
    }
    return lnfac
    }

    tableLock.Lock()
    defer tableLock.Unlock()
    lnFacTable = append(lnFacTable, make([]float64, x-l+1)...)
    for i := l; i < len(lnFacTable); i++ {
    lnfac += math.Log(float64(i))
    lnFacTable[i] = lnfac
    }

    return lnfac
    }



    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Dan Kortschak at Apr 9, 2013 at 5:57 am
    Nope. Just realised there is a possibility of l being changed between
    being read and used in growing the table. Need to think more.
    On Tue, 2013-04-09 at 15:19 +0930, Dan Kortschak wrote:
    On Tue, 2013-04-09 at 07:47 +0200, Rémy Oudompheng wrote:
    The RWMutex looks like the natural thing to use.
    Yeah. I initially thought so, then got tangled, but I think I have
    something that works now:

    func lnFac(x int) float64 {
    tableLock.RLock()
    l := len(lnFacTable)
    if x < l {
    defer tableLock.RUnlock()
    return lnFacTable[x]
    }
    lnfac := lnFacTable[l-1]
    tableLock.RUnlock()

    // New section to prevent excessive table growth.
    if x > maxTableLen {
    for i := float64(l); i <= float64(x); i++ {
    lnfac += math.Log(i)
    }
    return lnfac
    }

    tableLock.Lock()
    defer tableLock.Unlock()
    lnFacTable = append(lnFacTable, make([]float64, x-l+1)...)
    for i := l; i < len(lnFacTable); i++ {
    lnfac += math.Log(float64(i))
    lnFacTable[i] = lnfac
    }

    return lnfac
    }


    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Tamás Gulácsi at Apr 9, 2013 at 7:18 am
    Just thinking loudly:

    The problem is that you modify the memoization table with not just one
    value, but for every new value - and also use that table for computation,
    too.
    And because of append, the WHOLE underlying array may change. Maybe another
    structure for linking a list of reasonably sized arrays?
    And fill in whole chunks (append a whole populated array at once)?
    That way the already computed part won't change and don't have to lock!

    Regularly a memoization only appends (changes) one value at once, and don't
    modify old values as append does here.

    Tamás

    2013. április 9., kedd 7:51:01 UTC+2 időpontban kortschak a következőt írta:
    Nope. Just realised there is a possibility of l being changed between
    being read and used in growing the table. Need to think more.
    On Tue, 2013-04-09 at 15:19 +0930, Dan Kortschak wrote:
    On Tue, 2013-04-09 at 07:47 +0200, Rémy Oudompheng wrote:
    The RWMutex looks like the natural thing to use.
    Yeah. I initially thought so, then got tangled, but I think I have
    something that works now:

    func lnFac(x int) float64 {
    tableLock.RLock()
    l := len(lnFacTable)
    if x < l {
    defer tableLock.RUnlock()
    return lnFacTable[x]
    }
    lnfac := lnFacTable[l-1]
    tableLock.RUnlock()

    // New section to prevent excessive table growth.
    if x > maxTableLen {
    for i := float64(l); i <= float64(x); i++ {
    lnfac += math.Log(i)
    }
    return lnfac
    }

    tableLock.Lock()
    defer tableLock.Unlock()
    lnFacTable = append(lnFacTable, make([]float64, x-l+1)...)
    for i := l; i < len(lnFacTable); i++ {
    lnfac += math.Log(float64(i))
    lnFacTable[i] = lnfac
    }

    return lnfac
    }

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Dan Kortschak at Apr 9, 2013 at 7:14 am
    Yeah, that certainly is what I'm struggling with. Though I think you'll
    still need the lock - two calls which extend beyond the table are in a
    race.
    On Tue, 2013-04-09 at 00:11 -0700, Tamás Gulácsi wrote:
    Just thinking loudly:

    The problem is that you modify the memoization table with not just
    one
    value, but for every new value - and also use that table for
    computation,
    too.
    And because of append, the WHOLE underlying array may change. Maybe
    another
    structure for linking a list of reasonably sized arrays?
    And fill in whole chunks (append a whole populated array at once)?
    That way the already computed part won't change and don't have to
    lock!

    Regularly a memoization only appends (changes) one value at once, and
    don't
    modify old values as append does here.

    Tamás
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Gulácsi Tamás at Apr 9, 2013 at 7:19 am
    Yes, but that can be a simple lock (not sure about the bound check):

    // pseudocode
    if x > table.End { //not sure about this - maybe an RWLock must protect
    such check?
    mtx.Lock()
    if x > table.End { //still needs growing
    table.Grow()
    }
    mtx.Unlock()
    }
    // use table





    2013/4/9 Dan Kortschak <dan.kortschak@adelaide.edu.au>
    Yeah, that certainly is what I'm struggling with. Though I think you'll
    still need the lock - two calls which extend beyond the table are in a
    race.
    On Tue, 2013-04-09 at 00:11 -0700, Tamás Gulácsi wrote:
    Just thinking loudly:

    The problem is that you modify the memoization table with not just
    one
    value, but for every new value - and also use that table for
    computation,
    too.
    And because of append, the WHOLE underlying array may change. Maybe
    another
    structure for linking a list of reasonably sized arrays?
    And fill in whole chunks (append a whole populated array at once)?
    That way the already computed part won't change and don't have to
    lock!

    Regularly a memoization only appends (changes) one value at once, and
    don't
    modify old values as append does here.

    Tamás
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Dan Kortschak at Apr 9, 2013 at 7:06 am
    It feels like I need a lock that can be promoted from an RLock to a
    WLock if needed. But this seems too baroque.
    On Tue, 2013-04-09 at 07:47 +0200, Rémy Oudompheng wrote:
    The RWMutex looks like the natural thing to use.

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Rémy Oudompheng at Apr 9, 2013 at 7:21 am
    It's not only baroque, it is not possible to promote because virtually
    any code using that would deadlock immediately.

    Having to check invariants twice is the normal pattern.

    Some people have proposed wrappers that check the condition twice for
    you but it didn't really simplify code.

    Rémy.

    2013/4/9, Dan Kortschak <dan.kortschak@adelaide.edu.au>:
    It feels like I need a lock that can be promoted from an RLock to a
    WLock if needed. But this seems too baroque.
    On Tue, 2013-04-09 at 07:47 +0200, Rémy Oudompheng wrote:
    The RWMutex looks like the natural thing to use.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Dan Kortschak at Apr 9, 2013 at 7:21 am
    Good. Thanks - I was thinking about double checking but wasn't sure.

    I just did a timing diagram for the promotion - yes, I see what you
    mean.
    On Tue, 2013-04-09 at 09:15 +0200, Rémy Oudompheng wrote:
    It's not only baroque, it is not possible to promote because virtually
    any code using that would deadlock immediately.

    Having to check invariants twice is the normal pattern.

    Some people have proposed wrappers that check the condition twice for
    you but it didn't really simplify code.

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Bryan Matsuo at Apr 9, 2013 at 7:59 am
    There is no need to lock during the first length check (it's going to kill
    performance). If the slice you check is longer than you need then the slice
    you index (whether or not the same slice) long enough and cannot have been
    garbage collected.

    http://play.golang.org/p/lKvTPIVN3m
    On Tuesday, April 9, 2013 12:21:36 AM UTC-7, kortschak wrote:

    Good. Thanks - I was thinking about double checking but wasn't sure.

    I just did a timing diagram for the promotion - yes, I see what you
    mean.
    On Tue, 2013-04-09 at 09:15 +0200, Rémy Oudompheng wrote:
    It's not only baroque, it is not possible to promote because virtually
    any code using that would deadlock immediately.

    Having to check invariants twice is the normal pattern.

    Some people have proposed wrappers that check the condition twice for
    you but it didn't really simplify code.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Bryan Matsuo at Apr 9, 2013 at 8:15 am
    that was needlessly obscure. sorry. http://play.golang.org/p/GEOslw9NyG
    On Tuesday, April 9, 2013 12:59:44 AM UTC-7, Bryan Matsuo wrote:

    There is no need to lock during the first length check (it's going to kill
    performance). If the slice you check is longer than you need then the slice
    you index (whether or not the same slice) long enough and cannot have been
    garbage collected.

    http://play.golang.org/p/lKvTPIVN3m
    On Tuesday, April 9, 2013 12:21:36 AM UTC-7, kortschak wrote:

    Good. Thanks - I was thinking about double checking but wasn't sure.

    I just did a timing diagram for the promotion - yes, I see what you
    mean.
    On Tue, 2013-04-09 at 09:15 +0200, Rémy Oudompheng wrote:
    It's not only baroque, it is not possible to promote because virtually
    any code using that would deadlock immediately.

    Having to check invariants twice is the normal pattern.

    Some people have proposed wrappers that check the condition twice for
    you but it didn't really simplify code.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Rémy Oudompheng at Apr 9, 2013 at 9:34 am
    It is not safe to read len(table) while fill is called concurrently.

    Rémy.

    2013/4/9, Bryan Matsuo <bryan.matsuo@gmail.com>:
    that was needlessly obscure. sorry. http://play.golang.org/p/GEOslw9NyG
    On Tuesday, April 9, 2013 12:59:44 AM UTC-7, Bryan Matsuo wrote:

    There is no need to lock during the first length check (it's going to kill

    performance). If the slice you check is longer than you need then the
    slice
    you index (whether or not the same slice) long enough and cannot have been

    garbage collected.

    http://play.golang.org/p/lKvTPIVN3m
    On Tuesday, April 9, 2013 12:21:36 AM UTC-7, kortschak wrote:

    Good. Thanks - I was thinking about double checking but wasn't sure.

    I just did a timing diagram for the promotion - yes, I see what you
    mean.
    On Tue, 2013-04-09 at 09:15 +0200, Rémy Oudompheng wrote:
    It's not only baroque, it is not possible to promote because virtually

    any code using that would deadlock immediately.

    Having to check invariants twice is the normal pattern.

    Some people have proposed wrappers that check the condition twice for
    you but it didn't really simplify code.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Dan Kortschak at Apr 9, 2013 at 9:35 am
    I don't think that's true. Not protecting the read means that you are potentially reading a half filled internal slice struct with no guarantee of validity. What if the location holding the len value was previously storing something larger than both x and the actual len of the slice. Whether this panic is now dependent on whether that read wins the race and the order of operations in append, which is not specified.

    It's true that the lock on the fast path will impact performance, but most cases are not contentious, so it should not be that bad. I'll have a look.

    On 09/04/2013, at 5:29 PM, "Bryan Matsuo" wrote:

    There is no need to lock during the first length check (it's going to kill performance). If the slice you check is longer than you need then the slice you index (whether or not the same slice) long enough and cannot have been garbage collected.

    http://play.golang.org/p/lKvTPIVN3m

    On Tuesday, April 9, 2013 12:21:36 AM UTC-7, kortschak wrote:
    Good. Thanks - I was thinking about double checking but wasn't sure.

    I just did a timing diagram for the promotion - yes, I see what you
    mean.
    On Tue, 2013-04-09 at 09:15 +0200, Rémy Oudompheng wrote:
    It's not only baroque, it is not possible to promote because virtually
    any code using that would deadlock immediately.

    Having to check invariants twice is the normal pattern.

    Some people have proposed wrappers that check the condition twice for
    you but it didn't really simplify code.


    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com .
    For more options, visit https://groups.google.com/groups/opt_out.


    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Bryan Matsuo at Apr 10, 2013 at 3:46 am
    Ah, right. I forget that a slice is a struct with non-atomic assignment
    instead of a pointer to a struct. I don't think that the order of
    operations in append matters, just the struct layout in memory and the
    implementation of memcpy (or whatever golang implementation X uses).
    On Tuesday, April 9, 2013 2:35:00 AM UTC-7, kortschak wrote:

    I don't think that's true. Not protecting the read means that you are
    potentially reading a half filled internal slice struct with no guarantee
    of validity. What if the location holding the len value was previously
    storing something larger than both x and the actual len of the slice.
    Whether this panic is now dependent on whether that read wins the race and
    the order of operations in append, which is not specified.

    It's true that the lock on the fast path will impact performance, but
    most cases are not contentious, so it should not be that bad. I'll have a
    look.

    On 09/04/2013, at 5:29 PM, "Bryan Matsuo" wrote:

    There is no need to lock during the first length check (it's going to
    kill performance). If the slice you check is longer than you need then the
    slice you index (whether or not the same slice) long enough and cannot have
    been garbage collected.

    http://play.golang.org/p/lKvTPIVN3m
    On Tuesday, April 9, 2013 12:21:36 AM UTC-7, kortschak wrote:

    Good. Thanks - I was thinking about double checking but wasn't sure.

    I just did a timing diagram for the promotion - yes, I see what you
    mean.
    On Tue, 2013-04-09 at 09:15 +0200, Rémy Oudompheng wrote:
    It's not only baroque, it is not possible to promote because virtually
    any code using that would deadlock immediately.

    Having to check invariants twice is the normal pattern.

    Some people have proposed wrappers that check the condition twice for
    you but it didn't really simplify code.

    --
    You received this message because you are subscribed to the Google Groups
    "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an
    email to golang-nuts...@googlegroups.com <javascript:>.
    For more options, visit https://groups.google.com/groups/opt_out.


    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Dan Kortschak at Apr 24, 2013 at 3:54 am
    A follow up for this that indicates sometimes you should look around
    more.

    There is a good approximation for ln(x!) when x > 10000ish. Using this
    we get:


    const tableLength = 10000

    var lnFacTable = genLnFac(tableLength)

    func genLnFac(l int) (table []float64) {
    table = make([]float64, l)
    lnfac := 0.

    for i := 1; i < l; i++ {
    lnfac += math.Log(float64(i))
    table[i] = lnfac
    }

    return
    }

    const ln2pi = 1.8378770664093454835606594728112352797227949472755668 // from wolphramalpha

    func lnFac(x int) float64 {
    if x < len(lnFacTable) {
    return lnFacTable[x]
    }
    // use Sterling's approximation for queries outside the table:
    return (float64(x)+0.5)*math.Log(float64(x)) - float64(x) + ln2pi/2
    }


    Which is naturally thread safe since there is only one table write
    operation ever, so no locks are needed at all. This gives results that
    are within 1e-9 of the exact calculation according to my tests.

    Just in case someone needs to calculate ln(x!) in the future.

    Dan

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupgolang-nuts @
categoriesgo
postedApr 9, '13 at 3:00a
activeApr 24, '13 at 3:54a
posts20
users4
websitegolang.org

People

Translate

site design / logo © 2021 Grokbase