Register a SA Forums Account here!
JOINING THE SA FORUMS WILL REMOVE THIS BIG AD, THE ANNOYING UNDERLINED ADS, AND STUPID INTERSTITIAL ADS!!!

You can: log in, read the tech support FAQ, or request your lost password. This dumb message (and those ads) will appear on every screen until you register! Get rid of this crap by registering your own SA Forums Account and joining roughly 150,000 Goons, for the one-time price of $9.95! We charge money because it costs us money per month for bills, and since we don't believe in showing ads to our users, we try to make the money back through forum registrations.
 
  • Post
  • Reply
roomforthetuna
Mar 22, 2005

I don't need to know anything about virii! My CUSTOM PROGRAM keeps me protected! It's not like they'll try to come in through the Internet or something!

pseudorandom name posted:

And on little endian platforms that can do unaligned loads (i.e. x86), you can just cast the arbitrary char* to an int* and read it like normal.
Aren't we essentially just discussing the ntohl/htonl functions here?

Adbot
ADBOT LOVES YOU

FlyingDodo
Jan 22, 2005
Not Extinct
Say I have a tree and I want to be able to get something from the tree by getting a pointer/reference to an object in it, not a copy. Is there a way to prevent the objects from being modified? I know I could use a const pointer or reference but its still possible to cast it as a plain old pointer and then change the data the pointer is pointing at. This is bad because the object would no longer make sense in the place it is in the tree.

Is there someway to prevent this?

OddObserver
Apr 3, 2009

FlyingDodo posted:

Say I have a tree and I want to be able to get something from the tree by getting a pointer/reference to an object in it, not a copy. Is there a way to prevent the objects from being modified? I know I could use a const pointer or reference but its still possible to cast it as a plain old pointer and then change the data the pointer is pointing at. This is bad because the object would no longer make sense in the place it is in the tree.

Is there someway to prevent this?

As stated? No (modulo some crazy stuff like mprotect if the object is meant to be entirely readonly). But as an alternative, you could make use of a copy-on-write type to get a similar effect, though at cost of some refcount thrashing.

Zaxxon
Feb 14, 2004

Wir Tanzen Mekanik
I found my problem. It's that vectors aren't thread safe when they reallocate. Basically there were 2 threads to my program, the main thread and the audio thread. The lists of pokeys would get made in the main thread, then read in the audio thread, during reallocation the audio thread would get the new memory address without the pokeys in it.

I noticed this because if I made 4 pokeys, when the program crashed on bad pointers 1 or 2 of them in the vector would sometimes be correct, the rest would be garbage.

I guess I need to use a data structure like List or something which doesn't have to reallocate or do some other kind of thing to make the vectors safe.

Jabor
Jul 16, 2010

#1 Loser at SpaceChem

Zaxxon posted:

I guess I need to use a data structure like List or something which doesn't have to reallocate or do some other kind of thing to make the vectors safe.

The solution is to use some form of synchronization to ensure that nothing else is trying to read the vector while it's being modified.

pseudorandom name
May 6, 2007

roomforthetuna posted:

Aren't we essentially just discussing the ntohl/htonl functions here?

Nope, those just swap the byte order (if necessary). Unaligned memory accesses are another thing entirely.

Jabor
Jul 16, 2010

#1 Loser at SpaceChem

FlyingDodo posted:

Say I have a tree and I want to be able to get something from the tree by getting a pointer/reference to an object in it, not a copy. Is there a way to prevent the objects from being modified? I know I could use a const pointer or reference but its still possible to cast it as a plain old pointer and then change the data the pointer is pointing at. This is bad because the object would no longer make sense in the place it is in the tree.

Is there someway to prevent this?

If you can't assume that the code you're handing the pointer off to is going to respect constness, then your tree getting messed up is not the problem you should be addressing.

If you're writing an application, then you shouldn't be running untrusted and potentially malicious code with full privileges to mess about in your address space.

If you're writing a library, then if the user of your library doesn't respect your preconditions, your library no longer needs to guarantee any sort of "correct" behaviour.

wlokos
Nov 12, 2007

...
I'm having a weird issue with a program that's supposed to apply a Ceasar Cipher to a message. As in: http://en.wikipedia.org/wiki/Caesar_cipher

Basically, the code lets the user choose how many letters to shift the message by, and then takes the message that they input as a string called Message. I then shift each letter with a for loop, like so:

code:
message = GetString();
length = strlen(message);

for(i=0; i<length; i++) // Executes cipher, retains proper capitalization
{                       // and does not change spaces or punctuation.
    if(message[i]>='a' && message[i]<='z')
    {
        message[i] = message[i] + key;
        if (message[i] > 'z')
        message[i] = message[i] - 26;
    }
    if (message[i]>='A' && message[i]<='Z')
    {
        message[i] = message[i] + key;
        if (message[i] > 'Z')
        message[i] = message[i] - 26;
    }
}

printf("%s\n", message);
}
This feels like it *should* work. The uppercase letters are fine, but the lowercase ones are having a weird glitch that I don't understand. If I enter the program with a shift value of 15, here's what the output is:

input: abcdefghijklmnopqrstuvwxyz ABCDEFGHIJKLMNOPQRSTUVWXYZ

output: pqrstuvwxyzabcde?????????? PQRSTUVWXYZABCDEFGHIJKLMNO

The lines
code:
if (message[i] > 'z')
message[i] = message[i] - 26;
aren't working properly for lowercase letters, and I don't know why. It seems like the problem happens whenever the ASCII value goes above 127 (for example, 'q' has a value of 113, which plus 15 is 128 and that's where the problem starts... that's also when the ASCII table I'm looking at goes into the extended ASCII code, and maybe that's the problem? Do I need to recode it so it never has the chance to go above 127? If so, why?

NecroBob
Jul 29, 2003

pseudorandom name posted:

And on little endian platforms that can do unaligned loads (i.e. x86), you can just cast the arbitrary char* to an int* and read it like normal.

I tried doing something like that, but the number kept coming out all wrong. I think I might try just reading it as a byte buffer, not a char buffer, if the functions support it.

pseudorandom name
May 6, 2007

wlokos posted:

It seems like the problem happens whenever the ASCII value goes above 127 (for example, 'q' has a value of 113, which plus 15 is 128 and that's where the problem starts... that's also when the ASCII table I'm looking at goes into the extended ASCII code, and maybe that's the problem? Do I need to recode it so it never has the chance to go above 127? If so, why?

How many bits are in a char? What range of values can that number of bits hold?

Vino
Aug 11, 2010
To whomever suggested I set SO_SNDBUF to 0, thank you it fixed my problem.

wlokos
Nov 12, 2007

...

pseudorandom name posted:

How many bits are in a char? What range of values can that number of bits hold?

8. Which means that it can only store up to 127. Which means that I need to not let the lowercase value go above 127 or things will glitch up.

Thanks!

Zaxxon
Feb 14, 2004

Wir Tanzen Mekanik

Jabor posted:

The solution is to use some form of synchronization to ensure that nothing else is trying to read the vector while it's being modified.

Well the reason I think a list would be a good Idea is as follows. The audio thread exists as a callback which gets called at a specific rate, it's a function of hardware. If I simply lock the vector I will hear a gap in the sound until the audio is resumed.

If I use a list I can tack a new pokey onto the end and the ones that are already there won't be lost. I will just have 2 instead of 3 until the 3rd is ready.

Jabor
Jul 16, 2010

#1 Loser at SpaceChem

Zaxxon posted:

Well the reason I think a list would be a good Idea is as follows. The audio thread exists as a callback which gets called at a specific rate, it's a function of hardware. If I simply lock the vector I will hear a gap in the sound until the audio is resumed.

If I use a list I can tack a new pokey onto the end and the ones that are already there won't be lost. I will just have 2 instead of 3 until the 3rd is ready.

Seriously now, how fast are you planning on calling this? Adding an object to a vector is a fast operation, simply adding locking around that won't break your callback.

The only time you could potentially notice it is if a large reallocation happens and a lot of copying needs to be done. And you can get around that by reserving a large enough space up-front.

Note that reserving space up-front without adding locking doesn't actually solve your problem. Sure, it might deal with the most common symptom of your lack of thread-safety, but there's no guarantee that you've actually resolved the issue.

If you want a concurrent data structure, use a concurrent data structure instead of one that just seems concurrent when you test it. Grab, say, Intel's "Threading Building Blocks" library and use a Concurrent Vector or something.

Zaxxon
Feb 14, 2004

Wir Tanzen Mekanik

Jabor posted:

Seriously now, how fast are you planning on calling this? Adding an object to a vector is a fast operation, simply adding locking around that won't break your callback.

The only time you could potentially notice it is if a large reallocation happens and a lot of copying needs to be done. And you can get around that by reserving a large enough space up-front.

Note that reserving space up-front without adding locking doesn't actually solve your problem. Sure, it might deal with the most common symptom of your lack of thread-safety, but there's no guarantee that you've actually resolved the issue.

If you want a concurrent data structure, use a concurrent data structure instead of one that just seems concurrent when you test it. Grab, say, Intel's "Threading Building Blocks" library and use a Concurrent Vector or something.

The only reason I used a vector in the first place is because it felt like the simplest STL data structure I could iterate through. I don't really need any of the other properties of vectors, I don't require random access at all. A list really just makes as much sense, and if I find thread safety problems I can always add locking to the list addition.

Jabor
Jul 16, 2010

#1 Loser at SpaceChem

Zaxxon posted:

The only reason I used a vector in the first place is because it felt like the simplest STL data structure I could iterate through. I don't really need any of the other properties of vectors, I don't require random access at all. A list really just makes as much sense, and if I find thread safety problems I can always add locking to the list addition.

Don't put off dealing with concurrency issues until they actually show up - if you think everything's all fine but there's a race condition hidden in there, you can bet it will show up after you make some minor change elsewhere and be a complete bitch to track down and resolve.

There are plenty of concurrency libraries out there. If your design calls for multiple threads you need to have that in mind from the start rather than trying to hack on things to fix them when they break.

It costs you nothing to use new concurrent_list instead of new list, whereas it's potentially a lot of time saved debugging random threading issues.

Zaxxon
Feb 14, 2004

Wir Tanzen Mekanik

Jabor posted:

Don't put off dealing with concurrency issues until they actually show up - if you think everything's all fine but there's a race condition hidden in there, you can bet it will show up after you make some minor change elsewhere and be a complete bitch to track down and resolve.

There are plenty of concurrency libraries out there. If your design calls for multiple threads you need to have that in mind from the start rather than trying to hack on things to fix them when they break.

It costs you nothing to use new concurrent_list instead of new list, whereas it's potentially a lot of time saved debugging random threading issues.

well, here is the deal, I appreciate all the advice that you are giving me but the audio thread is not generated by me but by a library that works with the audio driver. I don't have anything like a thread handle or any kind of stuff like mutexs or semaphores that I know will work with the library (it doesn't have any built in concurrency stuff.) I'm not really sure what normal concurrency stuff would work in this situation.

Jabor
Jul 16, 2010

#1 Loser at SpaceChem

Zaxxon posted:

I'm not really sure what normal concurrency stuff would work in this situation.

Just use a concurrent collection instead of a regular one. If you're in a position to consider replacing a vector with a list, you're also capable of replacing it with a concurrent list.

Zaxxon
Feb 14, 2004

Wir Tanzen Mekanik

Jabor posted:

Just use a concurrent collection instead of a regular one. If you're in a position to consider replacing a vector with a list, you're also capable of replacing it with a concurrent list.

my only hesitation is that I don't give enough of a gently caress about this to go digging through a bunch of libraries to figure out if the whatnot that each individual library uses to make it's concurrent structures work is compatible with the rest of what I'm doing.

floWenoL
Oct 23, 2002

Zaxxon posted:

my only hesitation is that I don't give enough of a gently caress about this to go digging through a bunch of libraries to figure out if the whatnot that each individual library uses to make it's concurrent structures work is compatible with the rest of what I'm doing.

So you don't care that what you write actually works?

rjmccall
Sep 7, 2007

no worries friend
Fun Shoe
I don't know why you think you need to dig through the library to understand its internal concurrency control; it's sufficient to know that that control isn't extended to your code. Moving from a std::vector to a std::list only changes the symptoms; since it sounds like you're only inserting concurrently, you'll have lost data and memory leaks instead of outright crashes.

There are lockless concurrent queues based on linked lists if that's what you're looking for, but std::list ain't it.

Zaxxon
Feb 14, 2004

Wir Tanzen Mekanik

floWenoL posted:

So you don't care that what you write actually works?

I must not be expressing my self correctly. I'm just writing this for myself and I'd rather have something I can play with that makes noise than have a proper structrue where I can spawn as many pokeys as I want while the audio is running.

I didn't want to go download a bunch of libraries which would have some data structure that says "concurrent list" and use it only to find that either:

1) it didn't work and whatever synchronization stuff it used would trash my audio callback.

2) it sat their seeming to work, just like std::list does while still actually not working and having done me no good.

I can always make it so that you have to stop audio to spawn a new pokey. Or I can make a really simple data structure to house the new pokeys, i mean both std::vector and std::list have a lot of features I don't care about.

edit: so I thought about it a second and one thing I want to make clear is not that I'm disagreeing with yalls advice, I agree that std::list is not a solution to my problem.

Zaxxon fucked around with this message at 01:20 on Nov 27, 2010

Luminous
May 19, 2004

Girls
Games
Gains

Zaxxon posted:

I'd rather have something I can play with

You would have this if you would just do what has been offered to you.

Null Pointer
May 20, 2004

Oh no!

Zaxxon posted:

Or I can make a really simple data structure to house the new pokeys, i mean both std::vector and std::list have a lot of features I don't care about.
As previously mentioned: Intel's Threading Building Blocks is a fantastic library. It's easy, it's fast, and its containers are nearly drop-in replacements for their STL counterparts.

Concurrency is an extremely complex problem requiring large amounts of experience and specialized knowledge. No offense, but you are astronomically unlikely to be successful writing your own concurrent data structures from a cold start.

evensevenone
May 12, 2001
Glass is a solid.
Seriously, a major part of CS research right now is people writing new programming languages entirely because doing concurrency in the "traditional" languages is so difficult.

shrughes
Oct 11, 2008

(call/cc call/cc)
Concurrency is not even difficult in traditional languages. You just have to be not retarded. Sure there are some people who cry to their mommies because their type system can't prove their code correct in a concurrent world, but they and their research do not matter.

Lots of people already do things concurrently without any difficulty at all. There is so much concurrency in web servers I don't even know where to begin sperging. There are billions and billions of PHP programmers who write concurrent websites that work.

The solution to the concurrency problem is in libraries and programs and the practical application of wanton simplicity, not in programming languages. After all, the programming language feature that did the greatest job of making concurrency easier is garbage collection. Well maybe it was the subroutine.

The problem with attacking concurrency in programming languages is that it only works if the entire system is written in that programming language, and if the entire system stays within one computer. The thing is, if we look for programming languages that are good at concurrency, we find that the reason is in their VMs, not in their language. Java is pretty good at concurrency because it's memory-safe and has some concurrency primitives. Erlang is good at concurrency because you can make threads cheaply. GHC is good at concurrency for similar reasons. Go is good at concurrency (presumably) for the same reason, and in case you're wondering, it doesn't really have any programming language support for concurrency, unless you also think that C is really good at arithmetic because it has syntax for it. Edit: If you grepped the Go specification, you'd think it had as much support for concatenation as it did for concurrency.

shrughes fucked around with this message at 01:48 on Nov 28, 2010

Jabor
Jul 16, 2010

#1 Loser at SpaceChem

shrughes posted:

The problem with attacking concurrency in programming languages is that it only works if the entire system is written in that programming language, and if the entire system stays within one computer.

Not if we shift towards languages targeting distributed computing.

quote:

The thing is, if we look for programming languages that are good at concurrency, we find that the reason is in their VMs, not in their language.

If we arbitrarily limit ourselves to imperative languages then I guess so, but if we're willing to step outside that, there's a whole lot of auto-parallelization that can be done with things like logic programming that just isn't feasible with a purely imperative language.

Null Pointer
May 20, 2004

Oh no!

shrughes posted:

Concurrency is not even difficult in traditional languages. You just have to be not retarded. Sure there are some people who cry to their mommies because their type system can't prove their code correct in a concurrent world, but they and their research do not matter.

Let me guess: you either only own an in-order scalar CPU or you've been unusually lucky.

floWenoL
Oct 23, 2002

Null Pointer posted:

Let me guess: you either only own an in-order scalar CPU or you've been unusually lucky.

Or maybe he's not retarded.

That Turkey Story
Mar 30, 2003

floWenoL posted:

Or maybe he's not retarded.

Holy moly.

Null Pointer
May 20, 2004

Oh no!

floWenoL posted:

Or maybe he's not retarded.

I wouldn't be so quick to make that judgment.

Arguing that concurrency is easy because there are "billions and billions of PHP programmers who write concurrent websites that work" is absurd. Of course any idiot can stumble through concurrency when the solution has already been provided (e.g. PHP + SQL, languages and libraries that provide synchronization primitives and concurrent containers.) This fact has absolutely nothing to do with the challenge of implementing a concurrent data structure in a language like C or C++, especially in this specific situation where the person is refusing to use any existing library.

Any solution to this problem is going to be architecture-specific, it will generally be compiler-specific and creating this solution will require a lot more knowledge than most people have. If you honestly believe otherwise, please tell me where you work so I can avoid your company's products.

floWenoL
Oct 23, 2002

Null Pointer posted:

I wouldn't be so quick to make that judgment.

Arguing that concurrency is easy because there are "billions and billions of PHP programmers who write concurrent websites that work" is absurd. Of course any idiot can stumble through concurrency when the solution has already been provided (e.g. PHP + SQL, languages and libraries that provide synchronization primitives and concurrent containers.) This fact has absolutely nothing to do with the challenge of implementing a concurrent data structure in a language like C or C++, especially in this specific situation where the person is refusing to use any existing library.

Any solution to this problem is going to be architecture-specific, it will generally be compiler-specific and creating this solution will require a lot more knowledge than most people have. If you honestly believe otherwise, please tell me where you work so I can avoid your company's products.

That's a nice straw man you put up there.

Null Pointer
May 20, 2004

Oh no!

floWenoL posted:

That's a nice straw man you put up there.
And this is quibbling.

rjmccall
Sep 7, 2007

no worries friend
Fun Shoe
The vast majority of concurrency bugs can be solved in an architecture- and compiler-independent manner by protecting coarsely-defined critical sections with a lock. Deadlock is usually easy to avoid if you're careful about what code is evaluated within the lock. It's certainly not a trivial amount of education, but neither is it some unfathomably deep subject.

Obviously that's not going to be an optimal solution for most problems, and optimizing from there can require a pretty steep jump in expertise, but it's a manageable place to start.

A MIRACLE
Sep 17, 2007

All right. It's Saturday night; I have no date, a two-liter bottle of Shasta and my all-Rush mix-tape... Let's rock.

My professor wants me to write a hash table library for my data structures class using the following function declaration to create the table:
code:
void *hash_table_create(int data_size, unsigned int (*hash)(void *key, int tablesize), int (*compare_keys)(void *key1, void *key2))
As he was nice enough to never go over function pointers in class I have to ask, am I supposed to write these inner argument functions outside *hash_table_create? And how will it look when I call hash_table_create? If I'm asking too much could someone point me to a good tutorial on function pointers?

Dijkstracula
Mar 18, 2003

You can't spell 'vector field' without me, Professor!

A MIRACLE posted:

As he was nice enough to never go over function pointers in class I have to ask, am I supposed to write these inner argument functions outside *hash_table_create?

The example I always use for explaining function pointers is integration: Consider

code:

  1 #include <stdio.h>
  2 #include <math.h>
  3 
  4 double integrate(double (f)(double), double a, double b, double h)
  5 {
  6     double x = a;
  7     double tally = 0;
  8     while (x < b) {
  9         tally += f(x)*h;
 10         x += h;
 11     }
 12 
 13     return tally;
 14 }
 15 
 16 double parabola(double x)
 17 {
 18     return (x * x) + 1;
 19 }
 20 
 21 int main(int argc, char **argv)
 22 {
 23     printf("Integral of sin from 0 to pi/2: %f\n", integrate(sin, 0,1.57,0.001));
 24     printf("Integral of x^2 + 1 from 0 to 1: %f\n", integrate(parabola, 0, 1, 0.001));
 25     return 0;
 26 }
code:
tnathan@tnathan-desktop:~$ gcc -Wall -lm foo.c 
tnathan@tnathan-desktop:~$ ./a.out 
Integral of sin from 0 to pi/2: 0.999704
Integral of x^2 + 1 from 0 to 1: 1.332833
integrate is a function that takes, as its first argument, a function that takes a double and produces a double. When you call integrate, you simply specify the name of the function you wish to pass - as I've shown, it can either be a predefined function or one that you write, so long as the function's signature is correct; though for the particular hash table problem you're working on, I'm guessing the prof will try to hash variables of various kinds, which in turn means s/he will be supplying those functions. For instance, if s/he tries to hash a string, the comparison function will probably be strcmp. If s/he's trying to hash some sort of structure, a custom comparison function will have to be written, and so on.

A MIRACLE
Sep 17, 2007

All right. It's Saturday night; I have no date, a two-liter bottle of Shasta and my all-Rush mix-tape... Let's rock.

Thanks, that's a pretty clear example. I've already been given a hash function to use for this particular project:

code:
unsigned int hash(void *key, int tablesize)
{
  unsigned int total;
  int i;
  char *s = (char *)key;
  
  total = 0;
  for (i = 0; s[i] != '\0'; i++) {
    total = ((total << 5) + s[i]) % 10000001;
  }
  return total % tablesize;
}
So I just create a pointer to this function, and then pass it like so to hash_table_create?
code:
void * myHashTable = hash_table_create(SIZE, ptr2hashfn, ptr2cmprfn);
How do I get the address of a function? Like this?
code:
unsigned int *ptr2hashfn = &hash;

roomforthetuna
Mar 22, 2005

I don't need to know anything about virii! My CUSTOM PROGRAM keeps me protected! It's not like they'll try to come in through the Internet or something!

A MIRACLE posted:

code:
void *hash_table_create(int data_size, unsigned int (*hash)(void *key, int tablesize), int (*compare_keys)(void *key1, void *key2))
As he was nice enough to never go over function pointers in class I have to ask, am I supposed to write these inner argument functions outside *hash_table_create? And how will it look when I call hash_table_create? If I'm asking too much could someone point me to a good tutorial on function pointers?
To answer these questions more directly, yes, the functions are written outside the other function (if you're writing the functions at all). It'll look something like this:
code:
unsigned int hash_for_string(void *key,int tablesize) {
 //make an appropriate hash of a string here
}

unsigned int compare_keys_for_string(void *key1,void *key2) {
 return strcmp((char*)key1,(char*)key2); //or some other comparison method!
}

void *hash_table_create(int data_size, unsigned int (*hash)(void *key, int tablesize), int (*compare_keys)(void *key1, void *key2)) {
 //make a hash table structure of some sort here, setting 
 //the functions to whatever was passed as parameters
}

int main() {
 //and here's what it looks like when you call it and pass function pointers
 void *hashtable=hash_table_create(WHATEVER_SIZE, hash_for_string, compare_keys_for_string);
}
Edit for later questions:

quote:

So I just create a pointer to this function, and then pass it like so to hash_table_create?
A function name is already basically a pointer, so you don't need to "create a pointer".

quote:

How do I get the address of a function? Like this?
The function name is already effectively the address of a function. If you want to put it into a different variable, the variable should be of the appropriate type, so it'd be more like
code:
 unsigned int (*hash_function_pointer)(void *, int);
 hash_function_pointer=hash_string;
I personally use a typedef whenever I'm dealing with function pointers because it makes things a lot more readable if you can do it as HASHPOINTER var=function; (So I might have made a minor syntax error explaining this from memory, since it's not the way I usually do it.)

roomforthetuna fucked around with this message at 01:20 on Nov 29, 2010

A MIRACLE
Sep 17, 2007

All right. It's Saturday night; I have no date, a two-liter bottle of Shasta and my all-Rush mix-tape... Let's rock.

roomforthetuna posted:

A function name is already basically a pointer, so you don't need to "create a pointer".

Excellent, thanks.

Adbot
ADBOT LOVES YOU

Dijkstracula
Mar 18, 2003

You can't spell 'vector field' without me, Professor!

edit: durr, roomforthetuna covered this :downs:

  • 1
  • 2
  • 3
  • 4
  • 5
  • Post
  • Reply