我正在一个平台(training.olinfo.it)上做一些“家庭作业”,在这个平台上,给定一个特定的问题,你必须创建一个解决它的程序,而且它必须尊重内存和时间限制。
我试图解决的问题(bigsomma)如下:* 给定由N个整数组成的序列V0,V1,. VN-1,找出它们的和。* 时间限制:1秒内存限制:256 MiB
假设:对于每0 ≤ i ≤ N-1,N ≤ 50.000.000 −67 108 864 ≤ Vi ≤ 67 108 863
我已经解决了这个问题,执行时间大约为0.9秒。事实上,我试图进一步优化它。我提交问题的平台不支持异步阅读,也不支持线程和pthreads,但看起来fork()调用可以工作。所以,我设置了一个共享内存空间,有2个缓冲区和一些指针。子进程读取,而父进程计算总和。事实是,在本地和平台上编译时,如果一些优化(如-O2)被启用时,代码挂起,而当它们被关闭时,代码按预期工作。此外,平台使用“-O2”标志自动优化,所以别无选择
我写的代码:
#define _SVID_SOURCE
#include<stdio.h>
#include<unistd.h>
#include<fcntl.h>
#include<stdlib.h>
#include<stdbool.h>
#include<sys/wait.h>
#include<sys/ipc.h>
#include<sys/shm.h>
#include<assert.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#define buf_size 0x10000
void swap(void** a, void** b){
void* c=*a;
*a=*b;
*b=c;
}
long long somma(FILE *__restrict__ f){
size_t size_read;
long long sum=0;
int current=0, neg=0, temp=0;
//int fd=f->_fileno;
int fd=fileno(f);
char c;
key_t shm_key=ftok("bigsomma_async.c", 65);
bool *can_proceed;
bool *acknowledge_read;
size_t *size_read_ptr;
char* buf_1;
char* buf_2;
char** buf_1_ptr;
char** buf_2_ptr;
int shmid=shmget(shm_key,
sizeof(bool)+
sizeof(bool)+
sizeof(size_t)+
sizeof(char)*buf_size+
sizeof(char)*buf_size+
sizeof(char*)+
sizeof(char*)
, IPC_CREAT | 0777);
if (shmid == -1) {
perror("shmget");
return 1;
}
char* shared_mem=(char*)shmat(shmid, NULL, 0);
can_proceed=(bool*)shared_mem;
acknowledge_read=(bool*)(can_proceed+1);
size_read_ptr=(size_t*)(acknowledge_read+1);
buf_1=(char*)(size_read_ptr+1);
buf_2=(char*)(buf_1+buf_size);
buf_1_ptr=(char**)(buf_2+buf_size);
buf_2_ptr=(char**)(buf_1_ptr+1);
*can_proceed=true;
*acknowledge_read=true;
*size_read_ptr=1;
*buf_1_ptr=buf_1;
*buf_2_ptr=buf_2;
pid_t pfork=fork();
if(!pfork){
while(*size_read_ptr!=0){
while(!*acknowledge_read){}
*size_read_ptr=read(fd, buf_2, buf_size);
while(!*can_proceed){}
/*char* tmp=*buf_1_ptr;
*buf_1_ptr=*buf_2_ptr;
*buf_2_ptr=tmp;*/
swap((void**)buf_1_ptr, (void**)buf_2_ptr);
*can_proceed=false;
*acknowledge_read=false;
}
exit(0);
}else{
int size_read;
while(*size_read_ptr!=0){
while(*can_proceed){}
size_read=*size_read_ptr;
*acknowledge_read=true;
for(current=0; current<size_read; current++){
c=(*buf_1_ptr)[current];
if(c>='0'){
temp*=10;
temp+=c-'0';
}else if(c=='-'){
neg=-1;
}else{
sum+=temp*neg;
temp=0;
neg=1;
}
}
*can_proceed=true;
}
}
wait(NULL);
shmdt(shared_mem);
shmctl(shmid, IPC_RMID, NULL);
return sum+temp*neg;
}
字符串
看看我的任务管理器的性能,我假设停止执行的原因是两个进程都卡在了while循环中。在使用gdb调试时,我注意到程序完全跳过了一些指针的声明,特别是布尔型指针。这是第一次在进程之间使用共享内存,如果我写了一些不安全的代码,我不会感到惊讶。如果有人指出一个错误和/或一个解决方案,我会很感激。
2条答案
按热度按时间4xy9mtcn1#
许多编译器优化都基于这样的假设:如果通过左值标识的存储位置被导致或观察到持有某个值,那么在没有任何证据表明存储可能受到干扰的情况下,后续的观察将产生相同的值。除了一些最低要求之外,标准放弃管辖权,作为“实现质量”问题,关于什么形式的证据的问题,一个实现将承认为指示这种干扰的可能性。
如果一个左值有一个
volatile
限定符,这通常会被解释为要求编译器将与该特定左值相关联的存储视为受到外部更改或观察而不通知。在大多数编译器上,这些编译器被设计为适合低级编程任务,而不是基于clang或gcc,在对对象的两次访问之间发生的对 anything 的volatile write将被视为该对象的状态可能以编译器无法预期理解的方式被观察或修改的证据。然而,clang和gcc两者,将标准放弃对实施质量问题的管辖权视为暗示所有可能的处理都是同样好的,因此两者都故意对潜在干扰的证据视而不见。当使用clang或gcc时,如果存储位置可能通过clang或gcc不理解的方式更改,则必须:1.在整个程序中,使用C11中添加的“原子”类型,* 独占地 * 引用存储位置。
1.使用
volatile
限定的左值独占地访问存储位置。1.在任何使用“普通”左值读取存储的尝试之前和之后,使用“内存屏障”或“内存清除”指令 * 和 * 确保在这些指令之间没有任何东西可以改变存储的值。即使读取可以产生存储在两个内存清除或内存屏障指令之间的任何值,gcc(可能还有clang)有时会以一种与存储器可能 * 曾经 * 保存的任何值不一致的方式运行。例如,给定
int temp1 = *p;
,gcc有时会通过将使用temp
的位置重写为使用*p
来消除对temp1
的需要。根据程序需要做什么,上面的任何一种可能是最实用的方法,但是应该记住所有三种可能性。
jfewjypa2#
好吧,经过一些搜索,感谢@Jérôme Richard提供的建议,我设法消除了while循环的需要,因为布尔变量初始化为
true
,所以优化为while(true)
。显然,在共享内存空间中修改它们并不会阻止GCC优化它们。我使用了信号,特别是kill()
和sigwait()
函数,分别发送和等待信号。编辑:正如@Brendan所指出的,使用fork()的代码实际上更慢,这也是因为我提交的平台总结了所有进程的时间。无论如何,感谢大家的帮助。
最后的代码如下:
字符串