simple pointer operations (newbe)

[Anno Siegel]

Anno Siegel wrote:

I thought so, too, when stringification enters the picture they can be equal
only when their types and addresses are exactly the same. But still, hmm,
you cannot have references to two different types pointing to the same
memory address, of course, so on second thought the address is a unique key
alone.

Is this because of possible garbage collection, or scalars growing or
shrinking automagically?

No. Nothing that happens internally, except cloning at the start of
a new thread, changes the reference address of a Perl value.

If you bless a reference, the string associated with it will contain
the class name. Since a reference can be unblessd, then blessed into
one class, then into another over its lifetime, the way it stringifies
may change.

Hmm speaking of hash keys, my understanding based
on some other languages is that they must depend on the object's state to be
able to work consistantly.

You're digging too deep. Tassilo has explained very well the difference
in hash keys (strings) and the hash value (an integer) used internally.
We're only talking hash keys here.

Anno

 

[xhoster]

Anno Siegel wrote:

I thought so, too, when stringification enters the picture they can be
equal only when their types and addresses are exactly the same. But
still, hmm, you cannot have references to two different types pointing to
the same memory address, of course, so on second thought the address is a
unique key alone.

You can, if at least one of the referenced variables is no longer alive.
Then the address can be reused.

Hmm speaking of hash keys, my understanding
based on some other languages is that they must depend on the object's
state to be able to work consistantly.

They do not need to depend on the object's state. In fact, I would
say they even cannot depend on the object's state, depending on what you
want to use them for.

But if you use a stringified
memory address and the address changes later on independent of the
blessed thing's state, you cannot just dereference the same blessed
thingy to reuse it as a key in indexing.

You don't dereference thingies to use them as a key, you stringify them.

Many other languages let you
freely use objects or whatever else you like as hash keys. ARe there any
workarounds for Perl? One possibility that came to mind would be to use
Data:umper and compute a hash value based on the object's state. Can I
somehow access Perl's internal hashing function for keys to hash my own
data, similar to Java's hashCode method?

There is nothing to prevent you from defining a method named hashCode on
each of your classes in Perl. You could even probably make a module,
something like Tie::RefHash, that would invoke this method for you when
appropriate.

I do realize Perl is not the same as Java, far from it. Still browsing
the docs for the hashCode method for the Object class, I noticed this
contract for hashing which might be widely applicable. Quoting JDK 5.0:

- Whenever it is invoked on the same object more than once during an
execution of a Java application, the hashCode method must consistently
return the same integer, provided no information used in equals
comparisons on the object is modified. This integer need not remain
consistent from one execution of an application to another execution of
the same application.

Interesting, so the internal state may change and you're allowed to
return the same hash code as long as the equality of the object, as far
as the user goes, is not altered. Maybe my suggestion about simply
dumping the blessed thingy's internals isn't wise after all.

Depends on your intended to use.

- If two objects are equal according to the equals(Object) method, then
calling the hashCode method on each of the two objects must produce the
same integer result.

- It is not required that if two objects are unequal according to the
equals(java.lang.Object) method, then calling the hashCode method on each
of the two objects must produce distinct integer results. However, the
programmer should be aware that producing distinct integer results for
unequal objects may improve the performance of hashtables.

Hmmm don't these last two statements contradict each other?

No. I believe you have fallen into the fallacy of affirming the
consequent, or maybe it is denying the antecedent, or something akin to
them.

At least on
an initial read, the first seems to say that if two objects of the same
Class return the same boolean for equals, you must return the same hash
codes. However, the second one effectively mitigates the first by saying
that if they produce different boolean values for equals, they don't have
to produce different hashcodes. So as far as I can see, you cannot tell
based on the hash code whether two objects are equal. The hash codes can
be the same if they are and they can still be the same if they aren't.
What's the use of being able to use objects as hash keys then?
Performance.

Perhaps
I'm again missing something fundamental here.

Yes. You are missing the fact that calling query.equals on the ten objects
which happen to have the same hashcode as the query is a heck of a lot
faster than calling query.equals on the ten object with the same hash code
plus the 398_931 other objects in the hash table which do not have the same
hash code.

Xho

 

[Veli-Pekka Tätilä]

You are blurring the distinction between the key that is to be hashed
and the result of this hashing, namely the hash code.

Umm yes, the equals method in the Java example applies to the object to be
hashed but the hash code returned by that object is used as the index. Which
naturally leads to the question, what are hashed objects as keys good for if
anything? So far I haven't been able to think of any real good uses.

Think of a hash as an array where a key/value pair is stored inside one of
the array's element.

<code snipped>
Thanks for the explanation, actually I knew most of this already and yet
again realized my mistake only some time after having hit the send message
menu item. THe first good explanation I read on hashes was in the K&R book.
They say quite compactly that a hash is an array of pointers to linked lists
holding data. You index to this array based on a hash code computed from the
data to be hashed in some way, such as using modulo. And just the other day
I was reading the book Fundamentals of Database Systems, which also talks
about various collision resolving methods and indexing in general.

Which reminds me, why do most programming languages including Perl stop to
vectors and hashes as far as the fancy out-of-the-box data structures go?
Why not extend this to, say, B plus trees, among others, as people willl
have to code them sooner or later. Yep, I know there are B-trees for Perl, I
just read an excellent tutorial on one. But it would be nice to have
efficient, balanced tree structures available by default as modules,
especially as they aren't that trivial to implement well.

can now use a hash with only two buckets and yet store an arbitrary amount
of key/value pairs

Which reminds me what's the origin of the term bucket when talking about
Hashes? K&R didn't mention it so I was initially pretty confused when I saw
the term. As far as I've understood it, a bucket is just the head of a
linked list stored in the array.

 

[Tassilo v. Parseval]

Also sprach Veli-Pekka Tätilä:

Umm yes, the equals method in the Java example applies to the object to be
hashed but the hash code returned by that object is used as the index. Which
naturally leads to the question, what are hashed objects as keys good for if
anything? So far I haven't been able to think of any real good uses.

Nowadays they are commonly used for the implementation of inside-out
objects. Whenever you want to associate some additional data with an
object, the ability to use it as hash-key is useful.

<code snipped>
Thanks for the explanation, actually I knew most of this already and yet
again realized my mistake only some time after having hit the send message
menu item. THe first good explanation I read on hashes was in the K&R book.
They say quite compactly that a hash is an array of pointers to linked lists
holding data. You index to this array based on a hash code computed from the
data to be hashed in some way, such as using modulo. And just the other day
I was reading the book Fundamentals of Database Systems, which also talks
about various collision resolving methods and indexing in general.

Indeed. There are many different methods to resolve collisions. Another
common one gets away without using a linked list: On a collision, the
moduloed hash-code is simply incremented till a free array element has
been found. If you have a good hashing function which evenly distributes
keys across the array, this yields a similar performance but uses less
memory as all the overhead imposed by linked list is avoided. This can
be crucial on 64bit machines where a single pointer is already 8 bytes.

Which reminds me, why do most programming languages including Perl stop to
vectors and hashes as far as the fancy out-of-the-box data structures go?
Why not extend this to, say, B plus trees, among others, as people willl
have to code them sooner or later. Yep, I know there are B-trees for Perl, I
just read an excellent tutorial on one. But it would be nice to have
efficient, balanced tree structures available by default as modules,
especially as they aren't that trivial to implement well.

I believe the STL internally uses balanced trees for their
implementation of the 'map' container. One reason might be that it's
more difficult to built a B-tree type that is generic enough. When you
insert something into it, it's at first not clear where this element
ought to be added so you additionally need at least an additional
function argument that determines which of the child-branches to follow.

To me the B-tree is not so much a type but some mixture of data-type,
algorithm and arrangement of data in memory. Same with linked lists
which you rarely find in the core of a language. They could be used
behind the scenes to implement arrays or for collision handling in
hashes, but I don't see them as first class data-types.

Which reminds me what's the origin of the term bucket when talking about
Hashes? K&R didn't mention it so I was initially pretty confused when I saw
the term. As far as I've understood it, a bucket is just the head of a
linked list stored in the array.

For me a bucket is first and foremost just a container for something
with a more or less defined structure or size. I haven't come across a
usage where it would specifically denote the head element of a linked
list. Also, the perl source calls the containers for key/value pairs
buckets in various places (just grep hv.c).

Tassilo

 

[xhoster]

Which reminds me, why do most programming languages including Perl stop
to vectors and hashes as far as the fancy out-of-the-box data structures
go?

I think Java has ordered maps or something like that in the standard
libraries.

Why not extend this to, say, B plus trees, among others, as people
willl have to code them sooner or later.

The B+ tree is pretty much designed for disk-based access (although I
imagine you might get some benefit from the L1,L2 caches even for in-memory
implementations), which I think would make it a pretty unusual choice
for a primitive.

Aside from which, I've never felt the need to code them sooner or later.
Install Mysql, install DBI, bam--you have most of the indexing capabilities
you will need. I guess you don't have scrollable cursors.

Yep, I know there are B-trees
for Perl, I just read an excellent tutorial on one.

Which one?

But it would be nice
to have efficient, balanced tree structures available by default as
modules, especially as they aren't that trivial to implement well.

They also aren't trivial to implement generically. What page size do you
use? What ordering function do you use? Unique or non-unique? How do you
munge the language's syntax to allow range queries as a primitive?

Xho

 

[Uri Guttman]

TvP> Also sprach Veli-Pekka Tätilä:

TvP> Nowadays they are commonly used for the implementation of
TvP> inside-out objects. Whenever you want to associate some
TvP> additional data with an object, the ability to use it as hash-key
TvP> is useful.

i use refs as hash keys in several places. one is to track a set of refs
where you want to be able to add/delete them. these are usually objects
but there is no reason they couldn't be regular refs. an example is an
event loop where you need to track live events and be able to find them
all. a hash of those objects as key and value is perfect for that.

so just because someone can't see a good reason to use a certain idiom
doesn't mean they don't exist.

and i wouldn't call them hashed objects. a hash of objects (or refs) is
probably clearer and definitely more accurate.

uri

 

[Veli-Pekka Tätilä]

Nowadays they are commonly used for the implementation of inside-out
objects. Whenever you want to associate some additional data with an
object, the ability to use it as hash-key is useful.

Ok thanks for the explanation. I did some Googling and seems the term
inside-out object is used primarily in Perl but I might be wrong. Anyway, I
found an article which adviced one to use them for typo-safe attributes
which could be viewed as one form of deffensive programming. URL:

http://www.samag.com/documents/s=9979/sam0603g/0603g.htm

moduloed hash-code is simply incremented till a free array element has
been found.

Clever. Though this approach would require you to have a dynamic array,
which is no problem in Perl. K&R used a static array and linked lists,
though, mainly for demonstrational purposes, I suppose.

I believe the STL internally uses balanced trees for their
implementation of the 'map' container.

Nice to know. The map in C++ is pretty good, they even offer multimaps
unlike Perl. But then again multimaps are easy to build in Perl so this is
not a problem. Just another distinction between having somthing
out-of-the-box or with a little personal effort. I kind of like the Perl
approach as far as, say strings, go as most of the common utility functions
are rather trivial to build. Still I wish there were more list operations in
the core such as reduce and zip.

To me the B-tree is not so much a type but some mixture of data-type,
algorithm and arrangement of data

Depends on the context, I guess.

Same with linked lists which you rarely find in the core of a language

Except Lisp of course, but that's a bit of an oddity to begin with.

For me a bucket is first and foremost just a container for something

Ok I thought the use might be hash specific. I stand corrected now, thanks.

 

[Tassilo v. Parseval]

Also sprach Veli-Pekka Tätilä:

Ok thanks for the explanation. I did some Googling and seems the term
inside-out object is used primarily in Perl but I might be wrong. Anyway, I
found an article which adviced one to use them for typo-safe attributes
which could be viewed as one form of deffensive programming. URL:

http://www.samag.com/documents/s=9979/sam0603g/0603g.htm

Yes, inside-out indeed seems to be Perl-centric. On the other hand, it's
nothing that would have been invented by the Perl folks. They are a
variation on the flyweight-pattern where an object is a very lightweight
entity ($dummy in the above article) and it is used to look up the real
data from some static container outside the caller's scope.

Besides avoiding typos, they have some other advantages. One is that
subclassing becomes easier and safer as the access to an object's
innards happens exlusively through accessor methods.

Clever. Though this approach would require you to have a dynamic array,
which is no problem in Perl. K&R used a static array and linked lists,
though, mainly for demonstrational purposes, I suppose.

The array behind a hash is almost always dynamic in the sense that it
grows (usually in multiples of two). That usually happens according to a
ratio which gives a trade-off between speed and memory. The lower the
ratio, the faster the hash becomes but the more memory it will eat:

if ($self->num_pairs / $self->num_buckets > 0.75) {
$self->num_buckes <<= 1;
$self->resize();
$self->rehash_stored_pairs();
}

The increment of the hash-code happens modulo the array-length so if the
right edge of the array has been reached, it wraps around and starts
from the beginning.

Nice to know. The map in C++ is pretty good, they even offer multimaps
unlike Perl. But then again multimaps are easy to build in Perl so this is
not a problem. Just another distinction between having somthing
out-of-the-box or with a little personal effort. I kind of like the Perl
approach as far as, say strings, go as most of the common utility functions
are rather trivial to build. Still I wish there were more list operations in
the core such as reduce and zip.

These are in List::Util and List::MoreUtils respectively. Again it's a
trade-off between providing functionality in the core of a language and
bloat caused by too many keywords. I think PHP has a few hundred
keywords and certainly screwed up on that front. Perl might lack a few
but at least a normal human can learn all the keywords by heart.

Except Lisp of course, but that's a bit of an oddity to begin with.

But even LISP uses them only behind the scenes to implement the lists
the programmer sees and uses, right? Not that I would know much about
LISP anyway...

Tassilo

 

[Anno Siegel]

Also sprach Veli-Pekka Tätilä:

Yes, inside-out indeed seems to be Perl-centric. On the other hand, it's
nothing that would have been invented by the Perl folks. They are a
variation on the flyweight-pattern where an object is a very lightweight
entity ($dummy in the above article) and it is used to look up the real
data from some static container outside the caller's scope.

Besides avoiding typos, they have some other advantages. One is that
subclassing becomes easier and safer as the access to an object's
innards happens exlusively through accessor methods.

As a consequence, inside-out objects don't suffer from the type-dependency
other perl objects show. A standard hash class can only inherit easily
from another hash class, and only another hash class can easily inherit
from it. In contrast, any type of class can inherit from any number of
inside-out classes, and an inside-out class can inherit from one
foreign (non-inside-out) class. Multiple inheritance *from* foreign
classes involves the usual trickery, often basing inheritance on a
has-a relation.

The other big advantage of inside-out classes is that different classes
have separate lexical name spaces for their fields (properties, attributes,
object variables, whatever). Typo-safety is only a small side-aspect
of this. The main advantage is that classes don't have to co-ordinate
their internal field names (a fundamental breach of privacy), as is the
case with standard hash classes.

The reason why inside-out classes are such a big deal in Perl is that
other OO languages don't have different types of object (scalar, array,
hash, etc.) but implement only one. Also, name space separation is
usually built into a typical OO language and doesn't have to be
implemented by the user. So this particular type of light-weight
object doesn't have general advantages over other objects the way
it does in Perl.

If I had my way, I'd call what is known as inside-out classes simply
"free classes". Inside-out, besides being a mouthful, describes the
implementation in contrast to the standard implementation of hash
classes, which it has set out to make obsolete. That's bad politics.

Mathematicians call a group "free" when it has generators that are
independent of each other, without troublesome algebraic relations.
Similarly, inside-out classes are free from troublesome interrelations
of name spaces and object types.

Having free classes would make Perl the only language that has free
modules (another related mathematical term). But, as we say in
German, "Der Zug ist abgefahren" (That train is long gone).

Anno

 

[Uri Guttman]

e> Also sprach Uri Guttman:

e> Interesting that you mention this scenario because this usage (keeping
e> track of events and associated objects) was the very one I came across
e> just recently. They used it for debugging purpose to see if any objects
e> leaked which can be a pain to figure out in event-based programming.
e> They used a weakened hash lest they interfere with the garbage
e> collecting.

i don't use weakened refs there as my event design want explicit
destructor calls. i do have callback objects in many places and those
two could benefit from weak refs but i am not sure if i will switch to
using them. the discipline of explicit desctruction isn't much work and
the consistancy of the code (you always know when something gets
destroyed) makes it easier to follow.

e> It's both ambiguous as 'hash' can mean the data-type (in Perl at
e> least) or it can mean the return value of the hashing function
e> applied to the object. I think we're both referring to the latter.

hmm, i don't follow that. my usage is when i have a hash and use an
object (or ref) for both a (stringified) key and its value. i don't see
any call to a hashing function (other than inside the hash). but i could
be misunderstanding your words.

uri

 

[robic0]

Dirk Lehmann ([email protected]) wrote on MMMMDLXI September MCMXCIII
in <URL:
It wasn't the complete code:

######
#!/usr/local/bin/perl -w

use strict;

my $a = \12345;
print "\$a points to address $a and their is $$a\n\n";

my $b = [reverse(10..15)]; #equal to '$b = \(reverse(10..15))'

Eh, no.

$ perl -wle '$b = [reverse (10 .. 15)]; print ref $b'
ARRAY
$ perl -wle '$b = \(reverse (10 .. 15)); print ref $b'
SCALAR



Once again, Perl has references. Not pointers. And while the
stringification of a reference of an array contains a memory address,

A memory address, really? A physical memory address, or a virtual address
within the process space?

and that memory address is indeed the address of the array,

Really? How would you know that? Is it something percolated up from the
Perl C core?

address of the first element.

How can an address be known in Perl script? A literal number
isin't an address!

It's the address of a struct (the array)

No it isin't. If its a number, its an index.

of which one element points to an array of pointers of structures
containing scalars.

Perl is not C.

Right! Perl isin't C! If you program in C you may be used to thinking
in terms of addresses and contents. Just make sure you know what forum
your in.

robic0

 

[robic0]

How can I cast the scalar to a reference?

You should not even want to.

Just to expand on that it should be pointed out that (amongst several
of things) Perl's arrays are of dynamic size. This means the storage of
elements cannot be contiguous[1] in memory so even if you do drop into
C and fiddle directly with an SV* (which is perfectly possible) then
you still couldn't do pointer arithmetic to get from one element of an
array to another.

That isn't true.

A Perl array (see below) contains a C array (xav_alloc) that stores
pointers (AV*) to the array elements. That C array is always contiguous
(C doesn't have any other). If a (Perl-) array is extended, in general
the C array must be copied to a new location. Pointer arithmetic on
the array is entirely possible.

Your pretty basic in your C memory re-allocation example. I've been
doing C/C++ for 20 years. A level down and you can do custom memory
management outside of standard libraries.

The structure below is a fixed block, all thats needed is to re-assign
xav_array with a new address.

Pointer arithmatic on the array is possible in C.
char fifth_element = xav_array[5];
string var_element = xav_array[5+i];
*(xav_array+(2*i)) = var_element;

Pointer arithmatic, C, is not available from Perl !!

Stop trying to impress people with simple C in a Perl group.
These things are not remotely the same.
Unless you insinuate the C/C++ core of Perl is somehow accessable
from a Perl script.

If you want to get into complex C, we can do that as well.

 

[robic0]

A. Sinan Unur wrote:

How can I cast the scalar to a reference?

You should not even want to.

Just to expand on that it should be pointed out that (amongst several
of things) Perl's arrays are of dynamic size. This means the storage of
elements cannot be contiguous[1] in memory so even if you do drop into
C and fiddle directly with an SV* (which is perfectly possible) then
you still couldn't do pointer arithmetic to get from one element of an
array to another.

That isn't true.

A Perl array (see below) contains a C array (xav_alloc) that stores
pointers (AV*) to the array elements. That C array is always contiguous
(C doesn't have any other). If a (Perl-) array is extended, in general
the C array must be copied to a new location. Pointer arithmetic on
the array is entirely possible.

Your pretty basic in your C memory re-allocation example. I've been
doing C/C++ for 20 years. A level down and you can do custom memory
management outside of standard libraries.

The structure below is a fixed block, all thats needed is to re-assign
xav_array with a new address.

Pointer arithmatic on the array is possible in C.
char fifth_element = xav_array[5];
string var_element = xav_array[5+i];
*(xav_array+(2*i)) = var_element;

Pointer arithmatic, C, is not available from Perl !!

Stop trying to impress people with simple C in a Perl group.
These things are not remotely the same.
Unless you insinuate the C/C++ core of Perl is somehow accessable
from a Perl script.

......... After its compiled

 

[robic0]

Anno Siegel ([email protected]) wrote on MMMMDLXIII
September MCMXCIII in <URL:`'
`' A Perl array (see below) contains a C array (xav_alloc) that stores
`' pointers (AV*) to the array elements. That C array is always contiguous
^ SV*
`' (C doesn't have any other). If a (Perl-) array is extended, in general
`' the C array must be copied to a new location. Pointer arithmetic on
`' the array is entirely possible.

Yes, but the "address" of a Perl array reference isn't the address of
the first element of xav_alloc, nor is it xav_array. It is the address
of the xpvav.

With this statement its apparent, IQ's have gone down the shitter !!
There is *NO* goddamed *ADDRESS* in Perl !!!!!!!!!!!!

 

[Uri Guttman]

"r" == robic0 <robic0> writes:


r> A memory address, really? A physical memory address, or a virtual
r> address within the process space?

the point to the large space in your skull.

r> Really? How would you know that? Is it something percolated up from
r> the Perl C core?

he looked at the source? he has a brain (unlike you)?

r> How can an address be known in Perl script? A literal number
r> isin't an address!

you need to learn much more about perl before you can stop blathering
like that.

r> No it isin't. If its a number, its an index.

i think abigail knows a trifle amount more about perl than you. ok, a
lot more than a trifle.

r> Right! Perl isin't C! If you program in C you may be used to thinking
r> in terms of addresses and contents. Just make sure you know what forum
r> your in.

just make sure you know which of your schizo personalities is
controlling you at the moment.

uri

 

[Dr.Ruud]

Uri Guttman schreef:

[addressing r0b1co]
just make sure you know which of your schizo personalities is
controlling you at the moment.

I like to think that r0b1co is one of the many clever jokes by Abigail.
Same for Pur1Gur1. I need to be wrong of course.

 

[Uri Guttman]

R> Uri Guttman schreef:

[addressing r0b1co]
just make sure you know which of your schizo personalities is
controlling you at the moment.

R> I like to think that r0b1co is one of the many clever jokes by Abigail.
R> Same for Pur1Gur1. I need to be wrong of course.

knowing abigail (in person) i will say you are wrong. trolls like those
are always self *cough* taught and are immune to real logic. they learn
enough to bamboozle newbies but so quickly fall when confronted with
anyone who has a functioning neuron or two. what is interesting is how
robic claims to know c and reads some perl guts but is clueless about
how they relate. the fact that perl uses the a real c address as part of
the value (numeric or string) of references is total smart as it will
guarantee the uniqueness of the ref value since the ram address is also
unique. but don't try to explain it to robic as he know better.

uri

 

[Dr.Ruud]

Uri Guttman schreef:

the fact that perl uses the a
real c address as part of the value (numeric or string) of references
is total smart as it will guarantee the uniqueness of the ref value
since the ram address is also unique.

Well, unique until the allocated block is moved. Unless the address is
more like a handle. Or the block was allocated as fixed.

but don't try to explain it to
robic as he know better.

I haven't seen any of his (or her) postings for already a very long
time.

 

[Uri Guttman]

R> Uri Guttman schreef:
R> Well, unique until the allocated block is moved. Unless the address is
R> more like a handle. Or the block was allocated as fixed.

the sv (or whatever the internal thing the ref is) never get reallocated
as they are fixed sized. only the string/array/hash buffers get
reallocated as needed and they are pointed to by a member of the sv. so
the ref value will never change as long as the ref is valid (not garbage
collected).

uri

 

[Anno Siegel]

R> Uri Guttman schreef:

R> Well, unique until the allocated block is moved. Unless the address is
R> more like a handle. Or the block was allocated as fixed.

the sv (or whatever the internal thing the ref is) never get reallocated
as they are fixed sized. only the string/array/hash buffers get
reallocated as needed and they are pointed to by a member of the sv. so
the ref value will never change as long as the ref is valid (not garbage
collected).

There is one exception: On thread (ithread) creation, everything is
cloned and one of the branches wakes up with all refaddrs changed.

That's why some implementations of inside-out classes aren't thread-safe.
An object in a newly cloned thread will appear to have lost its data.
The problem is fixable, at a price.

As far as I'm concerned thread users get what they deserve and deserve
what they get

Anno