Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

Re^5: Bidirectional lookup algorithm? (Judy)

by BrowserUk (Patriarch)
on Jan 12, 2015 at 11:53 UTC ( [id://1112943]=note: print w/replies, xml ) Need Help??


in reply to Re^4: Bidirectional lookup algorithm? (Judy)
in thread Bidirectional lookup algorithm? (Updated: further info.)

From the Judy Arrays web page:

The Judy family of functions supports fully dynamic arrays. These arrays may be indexed by a 32- or 64-bit word (depending on processor word size), a null terminated string or an array-of-bytes plus length. A dynamic array (sparsely populated) can also be thought of as a mapping function or associative memory.

A Word_t is a typedef unsigned long int in Judy.h and must be the same size as sizeof(void *) I.E. a pointer.

unsigned long int is a 4-byte integer on 64-bit Windows.

This seems to be the 64-bit data model difference between Windows (LLP64) and *nix (LP64) raising its ugly head.

Word_t should be typedef'd as long long in order to ensure that sizeof(Word_t) == sizeof(void*) on both platforms.


With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked

Replies are listed 'Best First'.
Re^6: Bidirectional lookup algorithm? (Judy)
by syphilis (Archbishop) on Jan 12, 2015 at 12:40 UTC
    Word_t should be typedef'd as long long

    typedef'ing to unsigned long long reduces the number of "shift count >= width" warnings. I now see only warnings in relation to left shifts.
    Anyway, there's obviously something else that's not the right size. (Disappointing that the Judy developers haven't ported this correctly.)

    I'm thinking that the "initializer element is not constant" errors must arise from some other issue.
    Before I go digging myself, I'll wait for a bit and see if anonymonk (or anyone else) knows what needs to be done.

    Cheers,
    Rob
      I now see only warnings in relation to left shifts. Anyway, there's obviously something else that's not the right size. (Disappointing that the Judy developers haven't ported this correctly.)

      There is a heads-up in the Judy sources that might explain this.

      cJU_POP0MASK(7) is defined (in JudyCommon/JudyPrivateBranch.h:129) as:

      #define cJU_POP0MASK(cPopBytes) JU_LEASTBYTESMASK(cPopBytes)

      Which is defined (in:JudyCommon/JudyPrivate.h:413) as:

      #define JU_LEASTBYTESMASK(BYTES) \ ((0x100UL << (cJU_BITSPERBYTE * ((BYTES) - 1))) - 1)

      And that is preceded by this comment:

      // Note:  This macro has been problematic in the past to get right and to make
      // portable.  Its not OK on all systems to shift by the full word size.  This
      // macro should allow shifting by 1..N bytes, where N is the word size, but
      // should produce a compiler warning if the macro is called with Bytes == 0.
      

      Which may explain the continued warnings.


      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked
Re^6: Bidirectional lookup algorithm? (Judy)
by oiskuu (Hermit) on Jan 13, 2015 at 01:44 UTC

    A long long typedef would break your assumption on x32 ABI. Fortunately, there is a type that should fit the bill exactly. You can use typedef ptrdiff_t Word_t; (and ssize_t is almost always the same size as well).

    $ echo | gcc -mx32 -dM -E - | grep SIZEOF
    

    Funny about the JU_LEASTBYTESMASK macro—it still doesn't appear quite right. Diligently the BITSPERBYTE is incorporated, but then, in the same definition, the 0x100 constant assumes 8 bits per byte ...

      A long long typedef would break your assumption on x32 ABI.

      I meant (and thought I'd implied) "on 64-bit systems".

      But you are right, there are probably better choices.

      Fortunately, there is a type that should fit the bill exactly. You can use typedef ptrdiff_t Word_t;

      ptrdiff_t is described as: "Result of subtraction of two pointers.".

      Which means it is a signed type, which might have implications for the kind of bit manipulations -- shifts and masking -- the judy code performs.

      uintptr_t would probably be a better choice: "uintptr_t: An unsigned integer or unsigned __int64 version of intptr_t.".

      (and ssize_t is almost always the same size as well).

      There doesn't appear to be a ssize_t defined by the MS compiler.

      There's size_t defined as:"Result of sizeof operator.", (as used by Perl's STRLEN type), which seems to happily coexist with any of U32/I32 or U64/I64 variables as counters in your typical for loop.


      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked
      Funny about the JU_LEASTBYTESMASK macro—it still doesn't appear quite right

      Yes, and it seems to have some involvement in the errors that kill the build.
      In JudyInsArray.c we have:
      static Word_t subexp_mask[] = { 0, ~cJU_POP0MASK(1), ~cJU_POP0MASK(2), ~cJU_POP0MASK(3), #ifdef JU_64BIT ~cJU_POP0MASK(4), ~cJU_POP0MASK(5), ~cJU_POP0MASK(6), ~cJU_POP0MASK(7), #endif
      There's no problem with the first 5 elements listed there, but in relation to ~cJU_POP0MASK(5), ~cJU_POP0MASK(6) and ~cJU_POP0MASK(7) we get the error that they are not constant expressions ("initializer element is not constant"), thus breaking C's rules.

      And in JudyCommon/JudyPrivateBranch.h we find:
      #define cJU_POP0MASK(cPopBytes) JU_LEASTBYTESMASK(cPopBytes)
      Cheers,
      Rob

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://1112943]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others scrutinizing the Monastery: (5)
As of 2024-04-19 01:27 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found